2018 BACS Contest Replay G-GCD and LCM of 3 numbers

定義一個3元LCM為F(a,b,c)=a*b*c/(gcd(a,b,c);

給出F（a,b,c）和gcd（a,b,c) 求有多少組a,b,c （a<=b<=c)滿足上述條件

思路：如果合法能找到那麼a>=b*b;素數因子不大，考慮素數配置設定，配置設定的話

因為是滿足大小關系，那麼考慮ans1記錄目前3個數完全不一樣，ans2表示目前

數有2個一樣，是以對于相同的素因子分成兩份去配置設定即可

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int nmax=10000001;
ll prime[nmax+11],tot;
int notprime[nmax+11];
int  counter[nmax+11];
void get_prime()
{
    tot=1;
    for(ll i=2; i<=nmax; i++)
    {
        if(!notprime[i])
            prime[tot++]=i;
        for(int j=1; j<tot&&i*prime[j]<=nmax; ++j)
        {
            notprime[i*prime[j]]=1;
            if(i%prime[j]==0)   break;
        }
    }
}
int main()
{

    get_prime();
    int t,last;
    scanf("%d",&t);
    ll a,b,ans1,ans2,tans1,tans2;
    while(t--)
    {
        scanf("%I64d%I64d",&a,&b);
        memset(counter,0,sizeof(counter));
        for(int i=1; i<tot&&a!=1; i++)
        {
            while(a%prime[i]==0)
            {
                counter[i]++,a/=prime[i];
                last=i+1;
            }
        }
        prime[0]=1e9+7;
        if(a!=1)
        {
            counter[0]++;
            prime[0]=a;
        }
        bool flag=false;
        for(int i=0; i<tot&&b!=1; i++)
        {
            while(b%prime[i]==0)
            {
                counter[i]-=2,b/=prime[i];
                if(counter[i]<0)
                flag=true;
            }
        }
        if(b!=1)
            flag=true;
        if(flag)
        {
            cout<<"0"<<endl;
            continue;
        }
        if(b!=1)
        {
            printf("0\n");
            continue;
        }
        int start=tot;
        ans1=ans2=0;
        for(int i=0; i<last; i++)
        {
            if(counter[i])
            {
                for(int j=0; j<=counter[i]/2; j++)
                {
                    if(j==0||(counter[i]%2==0&&j==counter[i]/2)) ans2++;
                    else ans1++;
                }
                start=i+1;
                break;
            }
        }
        for(int i=start; i<last; i++)
        {
            tans1=ans1,tans2=ans2;
            if(counter[i])
            {
                ans1=0,ans2=0;
                for(int j=0; j<=counter[i]/2; j++)
                    if(j==0||(counter[i]%2==0&&j==counter[i]/2))ans1+=tans2,ans2+=tans2,ans1+=3*tans1;
                    else ans1+=3*tans2,ans1+=6*tans1;
            }
        }
        if(ans1+ans2==0)
            cout<<"1"<<endl;
        else
            cout<<ans1+ans2<<endl;
    }
}