hdu4497 正整数唯一分解定理应用

C - （例题）整数分解，计数

Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:65535KB     64bit IO Format:%I64d & %I64u

Submit Status

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

2 6 72 7 33

 

Sample Output

72 0

题目大意：

给你两个数L,G，问你有多少有序数组（x,y,z)满足GCD（x,y,z)=G,LCM(x,y,z)=L,首先如果gcd(x,y,z)=G,

那么有gcd(x/G,y/G,z/G)=1（说明这三个数两两互素），此时应该满足lcm(x,y,z)=L/G,要求L/G为整数，则若L%G==0，则一定有解，(x,y,z都等于L/G即可）

反之无解

此时将L/G作正整数唯一分解，T=L/G=a1^b1*a2^b2*.......*an^bn，对于a1，要满足gcd(x/g,y/g,z/g)=1，a1^k则至少有一个k=0,同时

还得满足lcm(x/g,y/g,z/g)=l/g,则至少有一个k=b1，这样就有三种情况（0，0，b1)(b1,b1,0)(0,1~b1-1,b1)共有6+6（b1-1)=6*b1种，其他的同理
由分步乘法计数原理，最终答案为(6*b1)*(6*b2)*........(6*bn)

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=2e5;//
bool vis[maxn];
ll prime[maxn/10];
int tot;
void getprime()//因为n的范围是1e14，打表只需要打到sqrt(n)即可，最多只可能有一个素因子大于sqrt(n)，最后特判一下即可；
{
    memset(vis,true,sizeof(vis));
    tot=0;
    for(ll i=2;i<maxn;i++)
    {
        if(vis[i])
        {
        prime[tot++]=i;
        for(ll j=i*i;j<maxn;j+=i)
        {
            vis[j]=false;
        }
        }
    }
}
/*void Eulerprime()
{
    memset(vis,true,sizeof(vis));
    int tot=0;
    for(int i=2;i<maxn;i++)
    {
        if(vis[i]) prime[tot++]=i;
        for(int j=0;j<tot&&prime[j]*i<maxn;j++)
        {
            vis[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
}*/
int a[1000],b[1000];
int cnt=0;
void sbreak(ll n)//正整数唯一分解
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    cnt=0;
    for(int i=0;prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]==0)
        {
            a[cnt]=prime[i];
            while(n%prime[i]==0)
            {
                b[cnt]++;
                n/=prime[i];
            }
            cnt++;
        }
    }
    if(n!=1)
    {
        a[cnt]=n;
        b[cnt]=1;
        cnt++;//为了使两种情况分解后素因子下标都是0~cnt-1;
    }
}
int pow_mod(int m,int n)
{
    ll pw=1;
    while(n)
    {
        if(n&1) pw*=m;
        m*=m;
        n/=2;
    }
    return pw;
}
int kase;
int main()
{
    int T;
    ll L,G;
    getprime();
    scanf("%d",&T);
    kase=0;
    while(T--)
    {
        scanf("%lld%lld",&G,&L);
        if(L%G) {printf("0
");continue;}
        ll n=L/G;
        sbreak(n);
        ll sum=1;
        for(int i=0;i<cnt;i++)
        {
            sum*=(6*b[i]);
        }
         printf("%lld
",sum);
    }
}