【HDU4497 GCD and LCM】

题意：已知l,g其中g=gcd(x,y,z),l=lcm(x,y,z),问有x，y，z多少种组合使得关系成立。
        题解：已知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) ...证明不出来
设 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 (不然最大公约数是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的次序不一样也算不同的结果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; }

 

总结

以上是生活随笔为你收集整理的【HDU4497 GCD and LCM】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。