UVa : 11889 (Benefit)



// http://uva.onlinejudge.org/external/118/11889.html
// Runtime : 0.320s
// Tag : Prime Factors, LCM

//===============================================================
// Name        : UVa_11889.cpp
// Author      : Shahab
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//===============================================================

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

bool mark [N];
vector <int> primeList;

void seive ()
{
	memset (mark, true, sizeof (mark));

	mark [0] = mark [1] = false;

	for ( int i = 4; i < N; i += 2 ) mark [i] = false;

	for ( int i = 3; i * i <= N; i += 2 ) {
		if ( mark [i] ) {
			for ( int j = i * i; j < N; j += 2 * i ) mark [j] = false;
		}
	}

	primeList.clear();
	primeList.push_back(2);

	for ( int i = 3; i < N; i += 2 ) {
		if ( mark [i] ) primeList.push_back(i);
	}
}

int power (int a, int b)
{
	int ret = 1;

	for ( int i = 1; i <= b; i++ ) ret *= a;

	return ret;
}

int factors (int a, int b)
{
	int ret = 1;
	int in = 0;
	int tmp = a;

	while ( primeList [in] * primeList [in] <= tmp ) {
		int cnt1 = 0;
		int cnt2 = 0;

		while ( a % primeList [in] == 0 ) {
			a /= primeList [in];
			cnt1++;
		}

		while ( b % primeList [in] == 0 ) {
			b /= primeList [in];
			cnt2++;
		}

		if ( cnt1 > cnt2 ) ret *= power (primeList [in], cnt1);

		in++;
	}

	if ( a > 1 && b == 1 ) ret *= a;

	return ret;
}

int main ()
{
	seive ();
	int testCase;
	scanf ("%d", &testCase);

	while ( testCase-- ) {
		int a, c;
		scanf ("%d %d", &a, &c);

		if ( c % a == 0 ) {
			printf ("%d\n", factors (c, a));
		}
		else printf ("NO SOLUTION\n");
	}

	return 0;
}

// @END_OF_SOURCE_CODE

3 thoughts on “UVa : 11889 (Benefit)

  1. are you sure those are critical input ?? cuz my program get’s the same outputs just checking if the divition of C/A is equal or not to (int)C/A, can you add more critical cases plz.

  2. @Bunk3r
    Output surely is not like, as u have said, C/A or (int)C/A
    i’ve provided some cases for you.

    Input:
    7
    8 32
    10 40
    12 72
    12 24
    36 216
    16 256
    40 240
    output:
    32
    8
    72
    8
    216
    256
    48
    

    at first attempt, i didn’t take care of cases, when output = C/A integer
    so i thought those could be perfect critical cases 😛
    now it seems like, i did a good idiotic job 😦

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s