传送门
感觉这题好难呢,全程抄代码
题解就懒得写了,推出式子后暴力+剪枝。反正不是自己想的
就安利大佬的博客吧:大佬的题解
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e5+10,p=20,mod=1e9+7;bool vis[maxn];
int a,b,c,T,d[maxn],pri[maxn],tot,f[30][30][30];
void prepare()
{
d[1]=1;
for(rg int i=2;i<=1e5;i++)
{
if(!vis[i])pri[++tot]=i,d[i]=2;
for(rg int j=1;j<=tot&&pri[j]*i<=1e5;j++)
{
vis[i*pri[j]]=1;
if(!(i%pri[j]))
{
d[i*pri[j]]=d[i]*d[pri[j]]-d[i/pri[j]];
break;
}
else d[i*pri[j]]=d[i]*d[pri[j]];
}
}
for(rg int i=1;i<=1e5;i++)(d[i]+=d[i-1])%=mod;
for(rg int i=1;i<=p;i++)
for(rg int j=1;j<=p;j++)
for(rg int k=1;k<=p;k++)
f[i][j][k]=f[i-1][j][k]+f[i][j-1][k]+f[i][j][k-1]-f[i][j-1][k-1]-
f[i-1][j-1][k]-f[i-1][j][k-1]+f[i-1][j-1][k-1]+d[i*j*k]-d[i*j*k-1];
}
long long solve(int now,int a,int b,int c)
{
if(!now)return 1ll*d[a]*d[b]*d[c]%mod;
if(pri[now]>max(max(a,b),c)&&max(max(a,b),c)<=p)return f[a][b][c];
int g=pri[now];long long ans=solve(now-1,a,b,c);
if(a>=g&&b>=g)ans-=solve(now-1,a/g,b/g,c);
if(a>=g&&c>=g)ans-=solve(now-1,a/g,b,c/g);
if(c>=g&&b>=g)ans-=solve(now-1,a,b/g,c/g);
if(a>=g&&c>=g&&b>=g)ans+=solve(now-1,a/g,b/g,c/g)*2;
return ans;
}
int main()
{
read(T),prepare();
while(T--)
{
read(a),read(b),read(c);int now=tot;
while(pri[now]>max(max(a,b),c))now--;
printf("%d\n",((solve(now,a,b,c)%mod)+mod)%mod);
}
}