[URI ONLINE JUDGE] – 2069 – Inês Venezuela’s Square Table

Inês Venezuela has decided to record on CD the videos she sent to GranHermano TV show, one video per CD. After putting each CD in a small square box, she realised that it was possible to organise the CDs in a manner that they would perfectly cover a square table of hers and no CD would be put over another CD.

Ana and Bob are two friends who are big fans of Inês Venezuela. They have also sent many videos to GranHermano and also recorded their videos on CDs, one video per CD. However, differently from Panterona (as Brazilians usually call Inês Venezuela), they want to organise their videos in knapsacks in a way that:

  • in each knapsack there are only CDs either from Ana or from Bob;
  • the number N of CDs in every knapsack is always the same.

They realised that there is not necessarily one possibility for the value of N, but, for all the possibilities of values for N, it would be also possible to organise all the Inês Venezuela’s CDs in knapsacks in a way that in each knapsack there would be exactly N Inês Venezuela’s CDs.

Knowing how many videos Ana and Bob have sent to GranHermano each, and knowing that the length of the side of each square box used by Inês Venezuela is 1 centimetre, calculate the length of the side of Inês Venezuela’s square table.

Input

The input consists only of two positive integers A and B (AB ≤ 109), which respectively represent the number of Ana’s CDs and the number of Bob’s CDs.

Output

Print how many centimetres long is the side of the Internet Queen’s square table. If there is more than one possible answer, print the smallest.

Input Samples Output Samples
18 24 6
60 140 10
588 420 42

 

Solution:

 

<br />#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll ele(ll x, ll y) {
ll res = 1;
for(int i = 0; i < y; i++) {
res *= x;
}
return res;
}

int main()
{

ll a, b;
cin >> a >> b;
ll ans = 1;
for(ll i = 2; i < 100000LL; i++) {
ll ea = 0, eb = 0;
while(a % i == 0) { ea++; a /= i; }
while(b % i == 0) { eb++; b /= i; }
ans *= ele(i, ((min(ea, eb) + (min(ea, eb) % 2)) / 2LL));
}

if(a == b) {
ans *= a;
}
printf("%lld\n", ans);

return 0;
}

Advertisements

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