P6825 「EZEC-4」求和题解

· · 个人记录

给定 n\le 1.5\times 10^6，求 \sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(i,j)^{i+j}，答案对质数 p 取模

推式子：

\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)^{i+j} =\sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}d^{d(i+j)}[\gcd(i,j)=1] =\sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}d^{d(i+j)}\sum_{k|\gcd(i,j)}\mu(k) =\sum_{d=1}^n\sum_{k=1}^{\frac{n}{d}}\mu(k)\sum_{i=1}^{\frac{n}{kd}}\sum_{j=1}^{\frac{n}{kd}}d^{kd(i+j)} =\sum_{d=1}^n\sum_{k=1}^{\frac{n}{d}}\mu(k)(d^{kd}+d^{2kd}+...+d^{\frac{n}{kd}\times kd})^2

发现可以后面是一个等比序列，可以 \log n 算，而前面是一个调和级数，时间复杂度为 n \ln n，故总时间复杂度是 O(n\ln n\log n)，可以过

上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1500050;
bool prime[N];
int zs[N],mu[N],idx;
int n,p,t[N];
void init()
{
    mu[1]=1;
    for(int i=2;i<=N-50;i++)
    {
        if(!prime[i]) zs[++idx]=i,mu[i]=-1;
        for(int j=1;j<=idx&&zs[j]*i<=N-50;j++)
        {
            prime[zs[j]*i]=true;
            if(i%zs[j]==0) break;
            mu[zs[j]*i]=-mu[i];
        }
    }
}
int ksm(int ds,int zs)
{
    ds=ds%p;
    int re=1;
    while(zs)
    {
        if(zs&1) re=1ll*re*ds%p;
        ds=1ll*ds*ds%p;
        zs=zs/2;
    }
    return re;
}
int calc(int x,int y)
{
    if(y==1) return x;
    int re=calc(x,y/2);
    re=(re+1ll*re*ksm(x,y/2)%p)%p;
    if(y&1) re=(re+1ll*x*ksm(x,y-1)%p)%p;
    return re;
}
int Calc(int x,int y)
{
    int re=calc(x,y);
    return 1ll*re*re%p;
}
int ssolve(int n,int d)
{
    int re=0;
    for(int l=1;l<=n;l++)
    {
        if(!mu[l]) continue;
        re=((re+1ll*mu[l]*Calc(ksm(d,l),n/l)%p)%p+p)%p;
    }
    return re;
}
int solve(int n)
{
    int re=0;
    for(int l=1;l<=n;l++)
        re=((re+ssolve(n/l,ksm(l,l)))%p+p)%p;
    return re;
}
int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&p);
        printf("%d\n",solve(n));
    }
    return 0;
}