gcd & lcm

gcd & lcm

欧几里得算法计算两数最大公约数和最小公倍数是常遇到的问题。现在写几个问题来回顾一下它的应用。hdu 1222 wolf and rabbit （gcd）题目：​​​#include #define LL long longusing namespace std;LL gcd(LL a, LL b){ return b?gcd(b,a%b):a;}int main(){ LL T,m,n; while(cin>>T){ while(T--){ LL f; scanf("%lld%lld",&m,&n); if(gcd(m,n)==1){ printf("NO\n"); } else printf("YES\n"); } } return 0;}

poj 2773 Happy 2006

题目：​​(1 <= m <= 1000000), K (1 <= K <= 100000000)，所以求出第k个互质数字要考虑到一种压缩方法，不要一个一个的暴力判断。

【曾经的思路：对于k的判断，可以用欧拉函数断定其范围，如果kth primer[k<=phi(m)]在m之内，则可以用fac[k]直接输出[m内,可以用素因子排除不互质的数字]。超出m的范围则直接用gcd() 或 素因子判断即可。但是这样TLE了。想用euler数组加二分，但是MLE。-_-怎么办？】

欧几里得算法含有的信息：gcd（b×t+a，b）=gcd（a，b）  （t为任意整数）

则如果a与b互素，则b×t+a与b也一定互素，如果a与b不互素，则b×t+a与b也一定不互素，故与m互素的数对m取模具有周期性。由此一来就可解决K较大时的情况。得到的信息：设m范围内的素数有k个，数字n对应至少有互质数n/m*k。当n是k的倍数时，对应的互质数：m*(n/k-1)+fac[k]. 当其不是倍数关系：n/k*m+fac[n%k]

#include #include using namespace std;typedef long long LL;const int maxn=1e6+5;int gcd(int a,int b){ return b?gcd(b,a%b):a;}int fac[maxn],top;int main(){ int m,n; while(cin>>m>>n){ top=0; for(int i=1;i<=m;i++){ //m可能等于1.所以要写<= if(gcd(m,i)==1) fac[++top]=i; } LL ans; if(n%top==0) ans=m*(n/top-1)+fac[top]; else ans=m*(n/top)+fac[n%top]; printf("%lld\n",ans); } return 0;}

zoj 1577 GCD & LCM

题目：​​& LCM

Time Limit: 2 Seconds     Memory Limit: 65536 KB

Given x and y (2 <= x <= 100,000, 2 <= y <= 1,000,000), you are to count the number of p and q such that:

1) p and q are positive integers;

2) GCD(p, q) = x;

3) LCM(p, q) = y.

Input

x and y, one line for each test.

Output

Number of pairs of p and q.

Sample Input

3 60

Sample Output

4

分析：GCD(p, q) = x; --> GCD(p/x,q/x)=1;

LCM(p, q) = y. --> LCM(p/x,q/x)=(p*q/x^2)/gcd(p/x,q/x)=p*q/x^2=y/x

设p/x,q/x分别是t1,t2. 有gcd(t1,t2)=1;  t1*t2=y/x=w  现在问题转换成寻找有多少对t1,t2互质且乘积就是w.

于是对w素因子分解，设w对应的因子展开式是(1+q1+q1^2+……+q1^n1)(1+q2+q2^2+……+q2^n2）……(1+qk+qk^2+……+qk^nk)，那么互质的两个乘积因子情况：qi^ni的组合数，即C(n,0)+C(n,1)+C(n,2)+……+C(n,n)=2^n。【不可能是qi^nj，其中0

#include #include #include using namespace std;int fac[1010],top;void resolve(int a){ top=0; for(int i=2;i*i<=a;i++){ if(a%i==0){ fac[top++]=i; while(a%i==0) a/=i; } } if(a>1) fac[top++]=a;}int power(int p){ int ans=1,temp=2; while(p){ if(p&1) ans=ans*temp; temp=temp*temp; p>>=1; } return ans;}int main(){ int x,y; while(cin>>x>>y){ if(y%x){ printf("0\n"); continue; } int w=y/x; resolve(w); printf("%d\n",power(top)); } return 0;}

hdu 1019 Least Common Multiple

​​#include using namespace std;int gcd(int a,int b){ return b?gcd(b,a%b):a;}int a[10000];int main(){ //freopen("cin.txt","r",stdin); int t,m; cin>>t; while(t--){ int g,ans=1; scanf("%d%d",&m,&a[0]); ans=a[0]; for(int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。