LCM is an abbreviation used for Least Common Multiple in Mathematics. We say LCM (a, b, c) = L if and only if L is the least integer which is divisible by a, b and c.
You will be given a, b and L. You have to find c such that LCM (a, b, c) = L. If there are several solutions, print the one where c is as small as possible. If there is no solution, report so.
Input
Input starts with an integer T (≤ 325), denoting the number of test cases.
Each case starts with a line containing three integers a b L (1 ≤ a, b ≤ 106, 1 ≤ L ≤ 1012).
Output
For each case, print the case number and the minimum possible value of c. If no solution is found, print 'impossible'.
Sample Input |
Output for Sample Input |
|
3 3 5 30 209475 6992 77086800 2 6 10 |
Case 1: 2 Case 2: 1 Case 3: impossible |
题意：lcm(a,b,c)=L;现已知a,b,L的值，求是否存在c满足lcm(a,b,c)=L。
::首先求出a,b的最小公倍数m,则c必包含因子t=L/m;
令g=gcd(c,m);
假设c=t，c*m/g=L,当且仅当gcd(c,m)=1等式成立;
如果gcd(c,m)>1；
那么令(c*g)*(m/g)/gcd(c*g,m/g)=L;当且仅当gcd(c*g,m/g)=1;
如果gcd(c*g,m/g)>1重复上述操作；
例：a=2,b=3,L=12;
则m=6,L=12,t=2;
令c=t;判断gcd(6,2)==2,令c=c*2(==4),m=m/2(==3)
gcd(c,m)==1,故c=4;
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b)
{
if(a < b)
swap(a,b);
return b == 0 ? a : gcd(b, a%b);
}
ll lcm(ll a, ll b)
{
return a / gcd(a, b) * b;
}
int main()
{
int T, cas;
ll a, b, l;
scanf("%d", &T);
cas = 0;
while(T--)
{
cas++;
scanf("%lld%lld%lld", &a, &b, &l);
ll m = lcm(a, b);
ll c = l / m;
if(m > l || l % m != 0)
{
printf("Case %d: impossible\n",cas);
continue;
}
ll g = gcd(c, m);
if(c != 1)
{
while(g != 1)
{
c *= g;
m /= g;
g = gcd(c, m);
}
}
printf("Case %d: %lld\n", cas, c);
}
return 0;
}