TLE代码来自http://uoj.ac/submission/110599

AC代码来自http://uoj.ac/submission/110933

推导如下：

设答案为ans，莫比乌斯函数为u，则

ans=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (gcd(i,j)==1&&gcd(j,k)==1) ans++;

莫比乌斯反演得

ans=0;
for (int j=1;j<=m;j++)
if (gcd(j,k)==1){
    for (int d=1;d<=j;d++)
    if (!(j%d)) ans+=u[d]*(n/d);
}

莫比乌斯反演得

ans=0;
for (int d=1;d<=n;d++)
if (gcd(d,k)==1){
    for (int j=d;j<=m;j+=d)
    if (gcd(j,k)==1) ans+=u[d]*(n/d);
}

定义函数如下:

int f(int x){
    int ans=0;
    for (int i=1;i<=k;i++)
    if (!(k%i)) ans+=u[i]*(x/i);
    return ans;
}

莫比乌斯反演得

ans=0;
for (int d=1;d<=n;d++)
if (gcd(d,k)==1) ans+=u[d]*(n/d)*f(m/d);

枚举t=gcd(d,k)，莫比乌斯反演得

for (int t=1;t<=k;t++)
if (!(k%t)&&u[t]){
    for (int d=t;d<=n;d+=t)
    ans+=u[t]*u[d]*(n/d)*f(m/d);
}

分块，设x=n/d，y=m/d。

for (int t=1;t<=k;t++)
if (!(k%t)&&u[t]){
    for (int d=t;d<=n;d+=t)
    ans+=x*f(y)*u[t]*u[d];
}

由积性得

for (int t=1;t<=k;t++)
if (!(k%t)&&u[t]){
    for (int d=t;d<=n;d+=t)
    if (gcd(d/t,t)==1) ans+=x*f(y)*u[d/t];
}

定义函数如下：

int sum(int x){
    int ans=0;
    for (int i=1;i<=x;i++)
    if (gcd(i,k)==1) ans+=u[i];
    return ans;
}

那么上述过程为

for (int t=1;t<=k;t++)
if (!(k%t)&&u[t]) ans+=x*f(y)*sum(n/t,k);

对sum函数，枚举gcd，莫比乌斯反演得

int sum(int x,int k){
    int ans=0;
    for (int t=1;t<=k;t++)
    if (!(t%k)){
        for (int d=1;d<=n/t;d++) ans+=u[t*d];
    }
    return ans;
}

由积性得

int sum(int x,int k){
    int ans=0;
    for (int t=1;t<=k;t++)
    if (!(t%k)) ans+=sum(n/t,t);
    return ans;
}

上述枚举为了易于理解，复杂度较高

不知道sum函数的复杂度是多少，希望神犇证明一下这个函数的时间复杂度。

这个似乎复杂度还可以，只是被卡常了。

在原代码基础上打了个小范围的记忆化就AC了。

TLE代码如下：

#include<cstdio>
const int N=1e6+10,SIZE=1e6;
typedef long long ll;
int n,m,k,u[N],p[N],cnt,s[N],v[2],q[N],size;
bool hash[N],vis[2][N];
ll su[2][N];
ll get_s(int x,bool y){
    return x<=SIZE?s[x]:su[y][v[y]/x];
}
void solve(int x,bool y){
    if (x<=SIZE) return;
    int t=v[y]/x;
    if (vis[y][t]) return;
    vis[y][t]=1;su[y][t]=1;
    int l,r=1;
    while (r<x){
        l=r+1;r=x/(x/l);
        solve(x/l,y);
        su[y][t]-=get_s(x/l,y)*(r-l+1);
    }
}
ll sum(int x,int k,bool y){//O(玄学) 
    if (!x) return 0;
    if (k==1) return get_s(x,y);
    ll ans=0;
    for (int i=1;i<=size&&q[i]<=k&&q[i]<=x;i++){
        int t=q[i];
        if (!(k%t)) ans+=sum(x/t,t,y);
    }
    return ans;
}
ll f(int x){//O(16)
    ll ans=0;
    for (int i=1;i<=size;i++) ans+=u[q[i]]*(x/q[i]);
    return ans;
}
int main()
{
    //freopen("cyclic.in","r",stdin);
    //freopen("cyclic.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    //杜教筛 
    u[1]=1;v[0]=n;v[1]=m;
    for (int i=2;i<=SIZE;i++){
        if (!hash[i]) p[++cnt]=i,u[i]=-1;
        for (int j=1;j<=cnt&&i*p[j]<=SIZE;j++){
            hash[i*p[j]]=1;
            if (i%p[j]) u[i*p[j]]=-u[i];
                else{u[i*p[j]]=0;break;}
        }
    }
    for (int i=1;i<=SIZE;i++) s[i]=s[i-1]+u[i];
    solve(n,0);solve(m,1);
    //质因子分解 
    for (int i=1;i<=k;i++)
    if (u[i]&&!(k%i)) q[++size]=i;
    //分块 
    int l=0,r=0;
    ll last=0,ans=0;
    while (l<n&&l<m){
        r=n/(n/(l+1));
        bool tag=0;//表示从n或m转移而来
        if (m/(m/(l+1))<r) r=m/(m/(l+1)),tag=1;
        int x=n/r,y=m/r;
        ll now=sum(r,k,tag);
        ans+=x*(now-last)*f(y);
        l=r;last=now;
    }
    printf("%lld\n",ans);
    return 0;
}

2021年5月2日填坑：

现在可以证明，$sum(n, k)$的时间复杂度是$O(\log^d n)$,其中d是k的不同质因子个数。证明如下：首先观察到，$sum$的时间复杂度关于$n$单调不减，关于$k$当质因子个数为$d$时，$k=\prod_{i=1}^d p_i$取到最大值，因此我们对它的时间复杂度进行放缩。$sum(n, k)$会调用$sum(\frac{n}{t}, t)$，设$j$有$j$个质因子，记$T(n, d)$为$sum(n, \prod_{i=1}^d p_i)$的时间复杂度，有 $$T(n, 1) = T(\frac{n}{2}, 1) + O(1) = O(\log n)$$ $$T(n, 2) <= T(\frac{n}{2}, 1) + T(\frac{n}{3}, 1) + T(\frac{n}{6}, 2) + O(1) = O(\log n) + T(\frac{n}{6}, 2) = O(\log^2 n)$$ 使用数学归纳法易得，当$d$是常数时，有$T(n, d) = O(\log^d n)$。因此算法复杂度瓶颈在筛法处，为$O(\max(n, m)^{\frac{2}{3}})$。