JinlinOJ 通化邀请赛 E．GCD and LCM 最大公约数最小公倍数关系-白红宇

JinlinOJ 通化邀请赛 E．GCD and LCM 最大公约数最小公倍数关系

阅读量：7282 次

发布时间：2019-06-30

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

首先我先给出一个他们之间的关系

最大公约数L和最小公倍数G的关系：

1、L%G == 0；

2、设A, B的最大公约数为G，最小公倍数为L，则：

L/G = （A/G）*（B/G）

3、gcd(A/G, B/G) = 1;

本题：

题意：给你三个数x,y,z的最大公约数gcd，最小公倍数lcm . 然后求满足的x,y,z有多少种可能。（1,3,2）和（1,2,3）被视为不同

思路：

首先lcm%gcd == 0是必须的，否则无解。然后将tmp = lcm/gcd 进行因式分解。假设其中有一个质因子p1的幂为e1，那么着三个数中至少有一个含有p1，至少有一个不含p1 。如果都含有p1的话他就被分到最大公约数里面去了，不会在tmp里面，如果不含有p1的话，那么p1就一定不会存在了。

那么对于质因子p1来说如果有两个含有他的话那么结果为A(3,2)*(e1 - 1) e1 可以分成x ,y (x+y = e1 x!=0 && y != 0) 如果有一个含有它的话那么必定是含有p1^e1次方。如果不是p1^e1次方的话，那么tmp里面的p1的幂也就不是e1了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define M 137#define N 5007#define ll long longusing namespace std;const double eps = 1e-10;int no[N];ll ans;int main(){// Read(); int T,i; scanf("%d",&T); ll gcd,lcm; while (T--) { cin>>gcd>>lcm; if (lcm%gcd != 0) printf("0\n"); else { CL(no,0); ll tmp = lcm/gcd; int len = 0; for (i = 2; i*i <= tmp; ++i) { if (tmp%i == 0) { len++; while (tmp%i == 0) { no[len]++; tmp /= i; } } } if (tmp > 1) no[++len] = 1; ans = 1; for (i = 1; i <= len; ++i) { ans = ans*(6 + 6*(no[i] - 1)); } cout<
                    
                     <

View Code

转载地址：http://kazjm.baihongyu.com/

你可能感兴趣的文章