hdu 4497(排列组合+LCM和GCD)

GCD and LCM

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 2024 Accepted Submission(s): 904

Problem Description

Given two positive integers G and L, could you tell me how many solutions of (x, y, z) there are, satisfying that gcd(x, y, z) = G and lcm(x, y, z) = L?
Note, gcd(x, y, z) means the greatest common divisor of x, y and z, while lcm(x, y, z) means the least common multiple of x, y and z.
Note 2, (1, 2, 3) and (1, 3, 2) are two different solutions.

Input

First line comes an integer T (T <= 12), telling the number of test cases.
The next T lines, each contains two positive 32-bit signed integers, G and L.
It’s guaranteed that each answer will fit in a 32-bit signed integer.

Output

For each test case, print one line with the number of solutions satisfying the conditions above.

Sample Input


72 
33 

Sample Output

72 
0

题解:首先我们要知道GCD和LCM的性质:

那么对gcd(a,b,c) GCD每个素因子上面也就是 min(xi,yi,zi) LCM 每个素因子上面就是 max(xi,yi,zi),我们先将LCM分解，然后用其每个素因子对GCD进行分解，如果分解之后GCD不为1，那么就肯定没有这样的组合。然后对每个素因子进行询问,假设当前的素因子是 p ，它的GCD指数是G,LCM的指数是L,如果G>L,那么肯定就不存在这样的组合了，如果G<L,那么第二大的数肯定就在 [L,G] 的区间内，当第二个数字位于(L,G)时,这三个数字有6种组合，当第二个数字等于L或者G时,三个数字有三种组合，所以每个因子的数的组合是 6*(L-G-1)+6=6*(L-G)种，如果L==G那么组合就是唯一的。最终的结果就是每个因子对应的组合数相乘。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 100000;
int p[N],e[N];
int p1[N],e1[N];
int main()
{
    int tcase;
    scanf("%d",&tcase);
    int a,b;
    while(tcase--){
        scanf("%d%d",&a,&b);
        int id=0,id1=0;
        memset(e,0,sizeof(e));
        memset(e1,0,sizeof(e1));
        for(int i=2;i*i<=b;i++){
            while(b%i==0){
                p1[id1]=i;
                while(b%i==0) {b/=i;e1[id1]++;}
                id1++;
            }
        }
        if(b>1) {p1[id1]=b;e1[id1++]=1;}
        for(int i=0;i<id1;i++){
            if(a%p1[i]==0){
                p[id] = p1[i];
                while(a%p1[i]==0){
                    a/=p1[i];
                    e[id]++;
                }
                id++;
            }
            else{
                p[id]=p[i];
                e[id++] = 0;
            }
        }
        if(a!=1){
            printf("0
");
            continue;
        }
        int sum = 1;
        bool flag = false;
        for(int i=0;i<id1;i++){
            if(e[i]<e1[i]){
                sum*=6*(e1[i]-e[i]);
            }
            if(e[i]>e1[i]) {
                flag = true;
                break;
            }
        }
        if(flag) {
            sum = 0;
        }
        printf("%d
",sum);
    }
    return 0;
}