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 3 3 5 30 209475 6992 77086800 2 6 10 Sample Output Case 1: 2 Case 2: 1 Case 3: impossible
#include <cstdio> #define ll long long ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b); } int main(){ int t; scanf("%d",&t); int kase = 1; while (t--){ ll a,b,c; ll lcm; scanf("%lld%lld%lld",&a,&b,&lcm); printf("Case %d: ",kase++); ll l1 = a*b/gcd(a,b); if (lcm%l1) { puts("impossible"); continue; } ll t; c = lcm/l1; 最后要保证正确的c要和lcm（a，b）/gcd（a，b）的gcd为1 while (gcd(l1,c)!=1){ t = c; c*=gcd(l1,c),l1/=gcd(l1,t); } printf("%lld\n",c); } return 0; }