题目概述

咕咕咕。求 $f(a,b)={\varphi(ab)\over\varphi(a)\varphi(b)},\sum_{a=1}^{n}\sum_{b=1}^{m}f(a,b)$ 。

解题报告

我只会做斯波题啊……显然 $(a,b)=d$ 的时候答案固定，令答案为 $g(d)$ ，那么就变成非常裸的莫比乌斯函数题……

没卡常会T……卡卡常就过了……

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000000;

int te,n,m,MOD,num[maxn+5],P[maxn+5][10],INV[maxn+5],orz[maxn+5],ans;
int p[maxn+5],mu[maxn+5];bool pri[maxn+5];

inline void Make(int n){
    pri[0]=pri[1]=true;mu[1]=1;
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i,mu[i]=-1;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            if (i%p[j]) pri[t]=true,mu[t]=-mu[i]; else {pri[t]=true;mu[t]=0;break;}
    }
    for (int i=1;i<=p[0];i++) for (int j=p[i];j<=n;j+=p[i]) P[j][++num[j]]=p[i];
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (Make(maxn),scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&m,&MOD);ans=0;
        INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
        for (int i=1;i<=n;i++) orz[i]=(LL)(n/i)*(m/i)%MOD;
        for (int i=1;i<=n;i++){
            int F=1;LL sum=0;for (int j=1;j<=num[i];j++) F=(LL)F*P[i][j]%MOD*INV[P[i][j]-1]%MOD;
            for (int j=i;j<=n&&j<=m;j+=i) sum+=mu[j/i]*orz[j];sum=(sum%MOD+MOD)%MOD;AMOD(ans,sum*F%MOD);
        }printf("%d\n",ans);
    }
    return 0;
}