LightOj 1215 Finding LCM
Discription
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
本来感觉这个题太水了就不想写博客了2333,但是考虑到我马上要做的那个题可能要用到这个题 一个东西(但是回头再看这句话时突然打脸),所以还是写一下。
可以先求出lcm(a,b)=p,然后本质就是求一个 最小的 X 使得 lcm(X,p) = L。
无解很好判,只要p不是L的约数就无解。
考虑到lcm是对指数取max,而我们的目的是让X最小,所以我们可以让X在p和L次数相同的质因子上的次数取0,而在其他的质因子上取L在这上面的次数。
所以我们可以直接对 L/p 质因子分解, 然后 这里的质因子就是所有X要和L次数一样的质因子,只要把p和L/p在这上面的指数加起来就好啦。
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
int T,d[100],num=0;
ll a,b,L,ans=1; ll gcd(ll x,ll y){
return y?gcd(y,x%y):x;
} inline void dvd(ll x){
for(int i=2;i*(ll)i<=x;i++) if(!(x%i)){
d[++num]=i; ll pre=x;
while(!(x%i)) x/=i;
ans*=pre/x; if(x==1) break;
}
if(x!=1) d[++num]=x,ans*=x;
} inline void solve(){
for(int i=1;i<=num;i++){
ll pre=a;
while(!(a%d[i])) a/=d[i];
ans*=pre/a;
}
printf("%llu\n",ans);
} int main(){
scanf("%d",&T);
for(int i=1;i<=T;i++){
scanf("%llu%llu%llu",&a,&b,&L);
a=a*b/gcd(a,b);
printf("Case %d: ",i); num=0,ans=1;
if(L%a) puts("impossible");
else{
dvd(L/a);
solve();
}
} return 0;
}
最新文章
- .NET里简易实现AOP
- update maven之后jre被改成1.5的问题
- 域环境下装SQL SERVER的一次惨痛经历
- Java系列: 关于LinkedList的 ListIterator的add和remove
- Sqli-labs less 19
- html元素拖拽
- C# 我是个传奇的 using
- Python读写Json文件
- xml字符串转对象xml文件转对象
- python向config、ini文件读取写入
- 完整例子-正则控制input的输入
- 【AtCoder】ARC073
- 12.13 Daily Scrum
- PS想象的力量无限大,设计师的脑洞无限大!
- golang日志收集方案之ELK
- java多线程 --ConcurrentLinkedQueue 非阻塞 线程安全队列
- php-----utf8和gbk相互转换
- 3.rabbitmq 发布/订阅
- structure needs cleaning
- 求同余方程x^A=B(mod m)的解个数(原根与指标)
热门文章
- 学习ucosii要用到的几本书
- npm 安装express npm ERR! code UNABLE_TO_VERIFY_LEAF_SIGNATURE
- Angular Vue React 框架中的 CSS
- JAVA 消耗 CPU过高排查方法
- 【Codeforces Round #476 (Div. 2) [Thanks, Telegram!] C】Greedy Arkady
- luogu3690 【模板】Link Cut Tree (动态树)
- TOJ4277: Sequence 组合数学
- DefaultTransactionStatus源码
- Jboss性能调优
- layui.code代码装饰器