lightoj 1215 Finding LCM
链接：http://www.lightoj.com/volume_showproblem.php?problem=1215
题意：已知 a, b, l 和 lcm(a, b, c) = l ，求最小的 c 的值。
思路：先找 l 的素因子并判断此因子是否为 a, b 的素因子，如果是，则判断他们各自的欧拉值的大小。因为 c 最大可能等于 l 的值，所以刚开始先把 l 的值赋给 c 。
当 l 中的某个素因子的欧拉值（l）大于 a，b 中相同的素因子的欧拉值（a, b）时，c中肯定含有次素因子并且欧拉值（c >= l ），然而 c 是 l 的因子，所以（c <= l ), 所以 c == l ，不用进行处理。
当 l 中的某个素因子的欧拉值（l）等于(最大就是等于，不可能小于) a，b 中相同的素因子的欧拉值（a, b）时，c中不一定含有次素因子，当 c 要取最小时，就可以不含有这个素因子，所以就把 c 中的 此素因子除干净。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; typedef long long LL;
const int N = ;
bool tag[N];
int prime[];
int k = ;
LL a, b ,c, l; LL stein(LL a, LL b) //stein 公式求最大公约数
{
if(a < b) swap(a, b);
if(!b) return a;
if(!(a&) && !(b&)) return * stein(a>>, b>>);
if(!(a&)) return stein(a>>, b);
if(!(b&)) return stein(a, b>>);
return stein((a-b)>>, b);
}
//当然，你也可以用欧几里得
LL gcd(LL a, LL b)
{
return b ? gcd(b, a%b) : a;
} int euler(LL *n, int m) //计算欧拉函数: 此函数中 n 值的变化会传回原处
{
int e = ;
while(!((*n) % m))
e++, (*n) /= m;
return e;
} void prm() //素数表（线性素数筛法）
{
int i,j;
memset(tag, , sizeof(tag));
tag[] = , prime[k++] = ;
for(i = ; i < N; i += )
{
if(!tag[i]) prime[k++] = i;
for(j = ; j < k && i*prime[j] < N; ++j)
{
tag[i*prime[j]] = ;
if(i%prime[j] == ) break;
}
}
} void ct(int q) //计算c值
{
int i, cnta, cntb, cntL, cnt0, cs = ;
c = l; // c 最大可能等于c， 先赋值为c，遇到情况在做除法减小它
if(l % (a/stein(a,b)*b)) //不可能的情况：l 不是(a, b)的最小公倍数的倍数
{
printf("Case %d: impossible\n", q);
return;
}
for(i=; i < k && (prime[i] <= a || prime[i] <= b); i++) //
{
cnta = cntb = ;
if(!(l%prime[i])) //是某个素数倍数的时候
{
cntL = euler(&l, prime[i]); // l 部分欧拉函数值
if(!(a%prime[i])) // 当这个素数也是a 的因子的时候
cnta = euler(&a, prime[i]); // a 的部分欧拉函数值
if(!(b%prime[i])) //当这个素数也是b 的因子的时候
cntb = euler(&b,prime[i]); //同 a 的操作
cnt0 = cnta > cntb ? cnta : cntb; // 最小公倍数当然是取值较大欧拉值
/*
a，b里边因子的欧拉值肯定要小于等于l的相同的因子的欧拉值的，当相等时，c要取最小就必须不含此因子
当a, b 中的因子的欧拉值都小于l中的时，c中相同因子的欧拉值必须大于等于l中的值，最小当然取等于啦
这也是为什么下面的只处理等于的情况
*/
if(cntL == cnt0)
while(cnt0--)
c /= prime[i];
}
}
if(a > && euler(&l, a) <= ) c /= a; //当 a 中含有大于1000的素数时的处理a
if(b > && euler(&l, b) <= ) c /= b; //当 b 中含有大于1000的素数时的处理b
printf("Case %d: %lld\n", q, c);
} int main()
{
int t, q=;
prm();
scanf("%d", &t);
while(t--)
{
scanf("%lld%lld%lld", &a, &b, &l);
ct(q++);
}
return ;
}