题目
题目描述
时光匆匆，转眼间又是一年省选季……
这是小 $Q$ 同学第二次参加省队选拔赛。今年，小 $Q$ 痛定思痛，不再冒险偷取试题，而是通过练习旧试题提升个人实力。可是旧试题太多了，小 $Q$ 没日没夜地做题，却看不到前方的光明在哪里。
一天，因做题过度而疲惫入睡的小 $Q$ 梦到自己在考场上遇到了一道好像做过的题目，却怎么也想不起曾经自己是怎么解决它的，直到醒来还心有余悸。
小 $Q$ 眉头一皱，感觉事情不妙，于是他找到了你，希望你能教他解决这道题目。小 $Q$ 依稀记得题目要计算如下表达式的值。
$(\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}d(ijk))\mod(10^9+7)$
其中 $d(ijk)$ 表示 $i \times j \times k$ 的约数个数。
输入输出格式
输入格式：
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来 $T$ 行，每行描述一组测试数据，包含三个整数 $A, B$ 和 $C$，含义见题目描述。
输出格式：
对于每组测试数据，输出一行，包含一个整数，表示所求表达式的值。
输入输出样例
输入样例#1：
5
10 10 10
100 100 100
1000 1000 1000
10000 10000 10000
100000 100000 100000
输出样例#1：
11536
51103588
165949340
19234764
176764584
说明
对于 $30$ 分的数据，$1 ≤ A, B, C ≤ 5000$。
对于 $100$ 分的数据，$1 ≤ T ≤ 10, 1 ≤ A, B, C ≤ 10^5, 1 ≤ \sum{max(A, B, C)} ≤ 2 * 10^5$。
题解
首先有一道题看起来是弱化版
根据这道题中的公式，发现$d(ijk)$的$i,j,k$必须同时满足$\sum_{x\vert i}\sum_{y\vert jk}[\gcd(x,y)==1],\sum_{x\vert j}\sum_{y\vert ik}[\gcd(x,y)==1],\sum_{x\vert k}\sum_{y\vert ij}[\gcd(x,y)==1]$
所以有式子$d(ijk)=\sum_{x\vert i}\sum_{y\vert j}\sum_{z\vert k}[\gcd(i,j)==1][\gcd(i,k)==1][\gcd(j,k)==1]$
可以进一步化成$\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)=\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\left\lfloor\frac{A}{i}\right\rfloor\left\lfloor\frac{B}{j}\right\rfloor\left\lfloor\frac{C}{k}\right\rfloor[\gcd(i,j)==1][\gcd(i,k)==1][\gcd(j,k)==1]$
对于后面的东西可以化成$\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\left\lfloor\frac{A}{i}\right\rfloor\left\lfloor\frac{B}{j}\right\rfloor\left\lfloor\frac{C}{k}\right\rfloor\sum_{x\vert i\&x\vert j}\mu(x)\sum_{y\vert i\&y\vert k}\mu(y)\sum_{z\vert j\&z\vert k}\mu(z)$
可以换成枚举$x,y,z$的形式$\sum_{x=1}^{min(A,B)}\sum_{y=1}^{min(A,C)}\sum_{z=1}^{min(B,C)}\mu(x)\mu(y)\mu(z)\sum_{x\vert i\&y\vert i}\left\lfloor\frac{A}{i}\right\rfloor\sum_{x\vert j\&z\vert j}\left\lfloor\frac{B}{j}\right\rfloor\sum_{y\vert k\&z\vert k}\left\lfloor\frac{C}{k}\right\rfloor$
后面这三坨东西就是$\sum_{lcm(x,y)\vert i}\left\lfloor\frac{A}{i}\right\rfloor\sum_{lcm(x,z)\vert j}\left\lfloor\frac{B}{j}\right\rfloor\sum_{lcm(y,z)\vert k}\left\lfloor\frac{C}{k}\right\rfloor$
发现后面这个每一项都可以$O(n\log n)$处理出来
然后就$O(n^3)$枚举！因为最小的点也是$5000$你甚至可以得到$0$分的好成绩！
没事你起码优化了一个log
仔细观察这个式子，如果把每个数看成一个点，然后把两个点$x,y$连上边权为$lcm(x,y)$的边
这样如果把图中每一个三元环都找出来就可以得到答案了
$\mu=0$的点就不用连边了，$lcm>max(A,B,C)$的也不用连边了
这样的边数好像会减少很多，某大爷说不到最大数据$8e5$条边
可以枚举两个互质的数$x,y$然后再枚举一个公因数$z$，这样$xz$和$yz$之间就有一条边权为$xyz$的边
这样每个三元环$6$种情况计算就好了
可以先计算三个点相同的和两个点相同的情况
感觉过不了但是卡卡常跑的还挺快因为爆不了long long去了取模能快6s
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
# define X first
# define Y second
# define mp make_pair
# define Pi pair<int,int>
# define LL long long
using namespace std;
const int MAX=2e5+5,mod=1e9+7;
struct p{
int A,B,C;
}qu[15];
struct o{
int x,y,d;
}c[MAX*37];
int T,N,tot,num;
int du[MAX],mu[MAX],pm[MAX];
LL fa[MAX],fb[MAX],fc[MAX];
bool use[MAX];
Pi vis[MAX];
vector<Pi> vec[MAX];
int max(int a,int b) {return a>b?a:b;}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void ss()
{
mu[1]=1;
for(int i=2;i<=N;++i)
{
if(!use[i]) pm[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&pm[j]*i<=N;++j)
{
use[pm[j]*i]=1;
if(i%pm[j]==0) break;
mu[pm[j]*i]=-mu[i];
}
}
}
int gcd(int a,int b) {return b?gcd(b,a%b):a;}
int main()
{
T=read();
for(int i=1;i<=T;++i)
N=max(N,max(qu[i].A=read(),max(qu[i].B=read(),qu[i].C=read())));
ss();
for(int t=1,M,ans;t<=T;++t)
{
memset(du,0,sizeof(du));
num=ans=0,M=max(qu[t].A,max(qu[t].B,qu[t].C));
for(int i=1;i<=M;++i)
{
fa[i]=fb[i]=fc[i]=0,vec[i].clear();
for(int j=i;j<=M;j+=i)
fa[i]+=qu[t].A/j,fb[i]+=qu[t].B/j,fc[i]+=qu[t].C/j;
fa[i]%=mod,fb[i]%=mod,fc[i]%=mod;
}
for(int i=1;i<=M;++i)
if(mu[i]) (ans+=(mu[i]*mu[i]*mu[i]*fa[i]*fb[i]%mod*fc[i]%mod+mod)%mod)%=mod;
for(int i=1;i<=M;++i)
for(int k=1;i*k<=M;++k)
if(mu[i*k]) for(int j=1,x,y;i*j*k<=M;++j)
if(mu[j*k]&&gcd(i,j)==1&&i!=j)
{
x=i*k,y=j*k;
(ans+=(mu[x]*mu[x]*mu[y]*fa[i*j*k]*fb[i*j*k]%mod*fc[x]%mod+mod)%mod)%=mod;
(ans+=(mu[x]*mu[x]*mu[y]*fa[i*j*k]*fc[i*j*k]%mod*fb[x]%mod+mod)%mod)%=mod;
(ans+=(mu[x]*mu[x]*mu[y]*fb[i*j*k]*fc[i*j*k]%mod*fa[x]%mod+mod)%mod)%=mod;
if(x<y) c[++num]=(o){x,y,i*j*k},++du[x],++du[y];
}
for(int i=1;i<=num;++i)
if(du[c[i].x]>du[c[i].y]) vec[c[i].x].push_back(mp(c[i].y,c[i].d));
else vec[c[i].y].push_back(mp(c[i].x,c[i].d));
for(int i=1;i<=M;++i)
if(mu[i])
{
for(int j=0,cnt=vec[i].size();j<cnt;++j)
vis[vec[i][j].X]=mp(i,vec[i][j].Y);
for(int j=0,cnt=vec[i].size();j<cnt;++j)
for(int k=0,x=vec[i][j].X,y,vi,vx,vy,cnt1=vec[x].size();k<cnt1;++k)
if(vis[vec[x][k].X].X==i)
{
y=vec[x][k].X,vi=vis[y].Y,vx=vec[x][k].Y,vy=vec[i][j].Y;
(ans+=(mu[i]*mu[x]*mu[y]*fa[vi]*fb[vx]%mod*fc[vy]%mod+mod)%mod)%=mod;
(ans+=(mu[i]*mu[x]*mu[y]*fa[vi]*fb[vy]%mod*fc[vx]%mod+mod)%mod)%=mod;
(ans+=(mu[i]*mu[x]*mu[y]*fa[vx]*fb[vi]%mod*fc[vy]%mod+mod)%mod)%=mod;
(ans+=(mu[i]*mu[x]*mu[y]*fa[vx]*fb[vy]%mod*fc[vi]%mod+mod)%mod)%=mod;
(ans+=(mu[i]*mu[x]*mu[y]*fa[vy]*fb[vx]%mod*fc[vi]%mod+mod)%mod)%=mod;
(ans+=(mu[i]*mu[x]*mu[y]*fa[vy]*fb[vi]%mod*fc[vx]%mod+mod)%mod)%=mod;
}
}
printf("%d\n",ans);
}
return 0;
}
