题解 CF1007B 【Pave the Parallelepiped】

liuyifan · 2018-12-23 09:38:33 · 题解

(部分内容转载自CF官方题解)

本人渣code:

#include<bits/stdc++.h>
#define reg register
#define ll long long
#define td (__gcd(__gcd(a,c),b))
using namespace std;
ll t,a,b,c,ab,bc,ac,f[100005]={1,1},num[100005],prime[100005],tot;
bool isprime[100005];
int main()
{
    for(reg int i=2;i<=100000;i++)
    {
        if(!isprime[i])
        {
            prime[++tot]=i;//质数 
            f[i]=2;
            num[i]=1;
        }
        for(reg int j=1;j<=tot&&i*prime[j]<=100000;j++)
        {
            isprime[i*prime[j]]=1;
            if(!(i%prime[j]))
            {
                num[i*prime[j]]=num[i]+1;
                f[i*prime[j]]=f[i]/(num[i]+1ll)*(num[i*prime[j]]+1ll);//预处理f数组
                break;
            }
            f[i*prime[j]]=f[i]*f[prime[j]];
            num[i*prime[j]]=1;
        }
    }//预处理 
    scanf("%lld",&t);//多组数据 
    while(t--)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        ab=__gcd(a,b);
        bc=__gcd(b,c);
        ac=__gcd(a,c);
        //__gcd:gcc内置gcd 
        ll ans1=f[a]*f[b]*f[c],ans2=(f[ab]*f[ab]-f[ab])/2ll*f[c],ans3=f[a]*(f[bc]*f[bc]-f[bc])/2ll,ans4=f[b]*(f[ac]*f[ac]-f[ac])/2ll,ans5=(f[td]*f[td]-f[td])+f[td]*(f[td]-1ll)*(f[td]-2ll)/6ll*4ll,ans6=(f[ab]-f[td])*f[td]*(f[td]-1ll)/2ll,ans7=(f[bc]-f[td])*f[td]*(f[td]-1ll)/2ll,ans8=(f[ac]-f[td])*f[td]*(f[td]-1ll)/2ll,ans9=(f[ab]-f[td])*(f[bc]-f[td])*(f[ac]-f[td]);
        //上述的几种情况 
        printf("%lld\n",ans1-ans2-ans3-ans4+ans5+ans6+ans7+ans8-ans9);//输出
    }
    return 0;
}