题目概述

求 $\sum_{i=1}^{n}\sum_{j=1}^{m}gcd^K(i,j)$ 。

解题报告

水题吧……先用莫比乌斯函数处理一下：

$$ \sum_{d=1}^{n}d^K\sum_{k=1}^{\lfloor min\{n,m\}\rfloor}\lfloor{n\over dk}\rfloor\lfloor{m\over dk}\rfloor\mu(k)\\ \sum_{T=1}^{n}\lfloor{n\over T}\rfloor\lfloor{m\over T}\rfloor\sum_{d|T}d^K\mu({T\over d}) $$

用线性筛预处理后面那个东西（调和级数会TLE），然后除法分块就行了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=5000000,MOD=1e9+7;

int te,K,n,m,p[maxn+5],pw[maxn+5],sum[maxn+5],ans;bool pri[maxn+5];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
inline void Make(int n){
    for (int i=1;i<=n;i++) pw[i]=Pow(i,K);
    for (int i=(sum[1]=1,2);i<=n;i++){
        if (!pri[i]) p[++p[0]]=i,sum[i]=ADD(pw[i],MOD-1);
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            if (i%p[j]) pri[t]=true,sum[t]=ADD(MOD-sum[i],MUL(sum[i],pw[p[j]]));
            else {pri[t]=true;sum[t]=MUL(sum[i],pw[p[j]]);break;}
    }for (int i=1;i<=n;i++) sum[i]=ADD(sum[i-1],sum[i]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d%d",&te,&K),Make(maxn);te;te--){
        scanf("%d%d",&n,&m);ans=0;
        for (int l=1,r;l<=n&&l<=m;l=r+1)
            r=min(n/(n/l),m/(m/l)),ans=ADD(ans,MUL(MUL(n/l,m/l),ADD(sum[r],MOD-sum[l-1])));
        printf("%d\n",ans);
    }return 0;
}