博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LightOj 1215 Finding LCM
阅读量:5015 次
发布时间:2019-06-12

本文共 1774 字,大约阅读时间需要 5 分钟。

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
#define ll unsigned long longusing 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;}

  

转载于:https://www.cnblogs.com/JYYHH/p/8530455.html

你可能感兴趣的文章
python 中安装pandas
查看>>
Hibernate 的<generator class="native"></generator>的不同属性含义
查看>>
linux修改root账户的用户名所得的教训
查看>>
【LeetCode】Flatten Binary Tree to Linked List
查看>>
读后感-浮生六纪
查看>>
执行指定路径的程序文件
查看>>
Leetcode-950 Reveal Cards In Increasing Order(按递增顺序显示卡牌)
查看>>
[Linux] 在 Linux CLI 使用 ssh-keygen 生成 RSA 密钥
查看>>
14款下载有用脚本的超酷网站
查看>>
LXC-Linux Containers介绍
查看>>
7.31实习培训日志-docker sql
查看>>
c#中使用servicestackredis操作redis
查看>>
ios app 真机crash报告分析
查看>>
CRC标准以及简记式
查看>>
SEO搜索引擎
查看>>
关于本地使用tomcat部署web应用,浏览器自动跳转为https的问题
查看>>
一、Text To Speech
查看>>
Java读取并下载网络文件
查看>>
github上构建自己的个人网站
查看>>
在word中粘贴的图片为什么显示不完整
查看>>