ICPC2019 南京网络赛 E（数论）

题目链接

感觉这道数论题挺好的，好多知识都用到了，前面推导过程有些套路，后面构造函数的过程有点难想

设

设

构造，有

由杜教筛，

因为是积性函数，可以先线性进行预处理，不难发现，对于质数，，然后对使用数论分块计算，设为每次数论分块的边界值，令

对于

设，讨论与的情况

注意k的值极大，求解需要使用欧拉定理进行降幂

不难证明复杂度为

#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
//using namespace std::tr1;
typedef long long int lli;
const int mod=1e9+7;
const int M=6e6+10;
char s[M];
lli n,k1,k2,g[M],ans;
int prime[M],vis[M];
unordered_map<lli,lli> sum;
void init()
{
    g[1]=1;
    for(int i=2;i<M;i++)
    {
        if(!vis[i])prime[++prime[0]]=i,g[i]=(1LL*i*i%mod-1+mod)%mod;
        for(int j=1;j<=prime[0]&&i*prime[j]<M;j++)
        {
            vis[prime[j]*i]=1;
            if(i%prime[j]==0)
            {
                g[i*prime[j]]=g[i]*prime[j]%mod*prime[j]%mod;
                break;
            }
            g[i*prime[j]]=g[i]*g[prime[j]]%mod;
        }
    }
    for(int i=1;i<M;i++)g[i]=(g[i]+g[i-1])%mod;
}
lli qpow(lli a,lli b)
{
    lli y=1;
    while(b)
    {
        if(b&1)y=y*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return y;
}
lli cal(lli q)
{
    if(q==1)return (k1-1+mod)%mod;
    return q*q%mod*(qpow(q,k2-1)-1+mod)%mod*qpow(q-1,mod-2)%mod;
}
lli ac(lli x)
{
    if(x<M)return g[x];
    if(sum[x])return sum[x];
    lli res=x*(x+1)%mod*(2*x%mod+1)%mod*qpow(6,mod-2)%mod;
    for(lli l=2,r=0;l<=x;l=r+1)
    {
        r=x/(x/l);
        res=(res-(r-l+1)%mod*ac(x/l)%mod+mod)%mod;
    }
    return sum[x]=res;
}
int main(int argc, char const *argv[])
{
    init();
    int t;scanf("%d",&t);
    while(t--)
    {
        k1=k2=ans=0;
        scanf("%lld%s",&n,s+1);
        for(int i=1;i<=strlen(s+1);i++)k1=(k1*10+s[i]-'0')%mod,k2=(k2*10+s[i]-'0')%(mod-1);
        for(lli l=1,r=0;l<=n;l=r+1)
        {
            r=n/(n/l);
            ans=(ans+(ac(r)-ac(l-1)+mod)%mod*cal(n/l)%mod)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}