GCD&LCM
1.青蛙的約會
題解：(x+mt)%L==(y+nt)%L等價於x-y+(m-n)t=kL
因此我們整理一下：(m-n)t+kL=y-x
a=m-n,b=L,c=y-x
在這裡需要注意a的值不為負，如果為負，則a=-a,c=-c
然後套用公式求出最小的t：t=(c/g*x%(b/g)+b/g)%(b/g)
程式碼：
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; ll extend_gcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } ll res=extend_gcd(b,a%b,x,y); ll tmp=x; x=y; y=tmp-(a/b)*y; return res; } int main() { ll i,j,x,y,m,n,l,a,b,c; cin>>x>>y>>m>>n>>l; a=m-n;b=l;c=y-x; if(a<0) { a=-a; c=-c; } ll g=extend_gcd(a,b,x,y); if(c%g!=0) { puts("Impossible"); } else { cout<<(c/g*x%(b/g)+b/g)%(b/g)<<endl; } return 0; }
2.Least Common Multiple
題目：//acm.hdu.edu.cn/showproblem.php?pid=1019
題解：每兩個之間求一遍lcm，一共球n次
程式碼：
#include<iostream> using namespace std; typedef long long ll; ll t,a[100000],n; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } ll lcm(ll a,ll b) { return a*b/gcd(a,b); } int main() { ll i,j; cin>>t; while(t--) { cin>>n; for(i=0;i<n;i++) cin>>a[i]; ll res=a[0]; for(i=1;i<n;i++) { res=lcm(res,a[i]); } cout<<res<<endl; } return 0; }
3. A/B
題目：//acm.hdu.edu.cn/showproblem.php?pid=1576
題解：逆元的應用
程式碼：
#include<iostream> using namespace std; typedef long long ll; ll extend_gcd(ll a,ll b,ll& x,ll& y) { if(b==0) { x=1; y=0; return a; } ll res=extend_gcd(b,a%b,x,y); ll tmp=x; x=y; y=tmp-(a/b)*y; } ll mod_inverse(ll a,ll m) { ll x,y; extend_gcd(a,m,x,y); return (m+x%m)%m; } int main() { ll i,j,t,n,b; ll mod=9973; cin>>t; while(t--) { cin>>n>>b; cout<<(n*mod_inverse(b,mod))%9973<<endl; } return 0; }
4.又見GCD
題目：//acm.hdu.edu.cn/showproblem.php?pid=2504
題解：a和c的最大公約數為b，因此c的選取從2*b開始，與a計算gcd，如果不是b就加b，如此往複
程式碼：
#include<iostream> using namespace std; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int main() { int i,j,n,a,b,c; cin>>n; while(n--) { cin>>a>>b; c=b*2; while(gcd(a,c)!=b) { c+=b; } cout<<c<<endl; } return 0; }
5.GCD
題目：//acm.hdu.edu.cn/showproblem.php?pid=2588
題解：
給定N,M求gcd(i,N)>=M的i的個數
我們可以分解N=a*b, i=a*d(b>=d 且b，d互質)，那麼我們要求的就是a》=m的時候d的個數（b隨a而確定）
由於b>=d且b，d互質，所以這個數目就是φ（b）-1
但是，如果對於每個a枚舉b，鐵定超時。（仍然O((N-M)*sqrt(N))的複雜度）
但是如果單純這樣全部枚舉的話依舊會超時，所以我們要想一個辦法去優化它。
我們可以折半枚舉，這裡的折半並不是二分的意思。
我們先看，我們枚舉時，當i<sqrt(n),假設a=n / i， 當i>sqrt(n)之後 有b=n/i，我們觀察到當n%i==0時，會出現一種情況，就是a*b==n。所以我們就可以只需要枚舉sqrt(n)種情況，然後和它對應的情況就是 n/i。
我們這種枚舉時間會快非常多
程式碼：
#include<iostream> #include<cmath> using namespace std; typedef long long ll; ll phi(ll n) { ll ans=n; for(ll i=2;i<=sqrt(n);i++) { if(n%i==0) { ans=ans/i*(i-1); while(n%i==0) n/=i; } } if(n>1) ans=ans/n*(n-1); return ans; } int main() { int t; ll n,m; cin>>t; while(t--) { cin>>n>>m; ll ans=0; for(ll i=1;i*i<=n;i++) { if(n%i==0) { if(i>=m) ans+=phi(n/i);//計算sqrt(n)左邊的 if(i*i!=n&&n/i>=m) ans+=phi(i);//計算計算sqrt(n)右邊的i*i==n時，在上個語句已經執行 （避免）完全平方算兩次 } } cout<<ans<<endl; } return 0; }
