題意：已知l,g其中g(shù)=gcd(x,y,z),l=lcm(x,y,z),問有x，y，z多少種組合使得關(guān)系成立。
? ? ? ? 題解：已知x%g=y%g=z%g=0，l%x=l%y=l%z=0,所以l%g=0。這個可以判定是否存在(x,y,z)符合條件。

gcd(a,b,c)=p; => gcd(a/p,b/p,c/p)=1 要不然gcd(a,b,c)>p
且 ?lcm(a/p,b/p,c/p) = lcm(a,b,c) / gcd(a,b,c) ...證明不出來
設(shè) lcm(a/p,b/p,c/p)=p1^d1*p2^d2.....pn^dn

? ? ? ? ? ? ? ? a/p=p1^a1*p2^a2.....pn^an

? ? ? ? ? ? ? ? b/p=p1^b1*p2^b2.....pn^bn

? ? ? ? ? ? ? ? c/p=p1^c1*p2^c2......pn^cn
? ?使得
? ? ? ? gcd(a/p,b/p,c/p)=1 則 min(ai,bi,ci)=0 ? ?max(ai,bi,ci)=di (不然最大公約數(shù)是pi^min(ai,bi,ci)*p>p，同理得到max(bi,ci,ai)=di) (uva10892只用到了max(ai,bi,ci)=di)
? ? 所以 (0，0，d1) (d1,d1,0) (0,1~d1-1,d1) 三種組合情況
? ? 則 ? C(3,1) ?+ ? ?C(3,1) ?+ ? (di-1)*A(3,3)=6*di ? ? ?a,b,c的次序不一樣也算不同的結(jié)果uva10892是去重了

?

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define X 10005 #define inf 0x3f3f3f3f #define PI 3.141592653589793238462643383 const int N=1e4; int main() {ios::sync_with_stdio(false);int primer[N],a[N],cnt=0;for(int i=2;i<sqrt(N);++i){if(!a[i]){primer[cnt++]=i;for(int j=i*i;j<N;j+=i){a[j]=1;}}}ll n,gcd,lcm;cin>>n;while(n--){cin>>gcd>>lcm;if(lcm%gcd)cout<<0<<endl;else{ll m=lcm/gcd,sum=1;for(int i=0;i<cnt&&primer[i]*primer[i]<=m;++i){int ant;if(m%primer[i]==0){ant=0;while(m%primer[i]==0){++ant;m/=primer[i];}sum*=6*ant;}}if(m>1)sum*=6;cout<<sum<<endl;}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU4497 GCD and LCM】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。