ICPC2019 南京网络赛 E（数论）

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

$f_{n}(k)=\sum_{l_{1}=1}^{n} \sum_{l_{2}=1}^{n} ... \sum_{l_{k}=1}^{n}(gcd(l_{1},l_{2}...l_{k}))^{2}$

$=\sum_{d=1}^{n}d^{2} \sum_{l_{1}=1}^{n/d} \sum_{l_{2}=1}^{n/d} ... \sum_{l_{k}=1}^{n/d} [gcd(l_{1},l_{2}...l_{k})==1]$

$=\sum_{d=1}^{n}d^{2} \sum_{l_{1}=1}^{n/d} \sum_{l_{2}=1}^{n/d} ... \sum_{l_{k}=1}^{n/d} \sum _{i|l_{1},i|l_{2}...i|l_{k}}\mu (i)$

$=\sum_{d=1}^{n}d^{2}\sum _{i=1}^{n/d}\mu (i)\left \lfloor \frac{n}{id}\right \rfloor^{k}$

设 $T=id$

$=\sum_{T=1}^{n}\left \lfloor \frac{n}{T}\right \rfloor^{k}\sum _{d|T}d^{2}\mu (\frac{T}{d})$

设 $g(T)=\sum _{d|T}d^{2}\mu (\frac{T}{d}),S(n)=\sum_{T=1}^{n}g(T)$

构造 $e(n)=1$ ，有 $g*e=\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}$

由杜教筛， $S(n)=\frac{n(n+1)(2n+1)}{6}-\sum_{d=2}^{n}S(\frac{n}{d})$

因为 $g$ 是积性函数，可以先线性进行预处理，不难发现 $g(1)=1$ ，对于质数 $p$ ， $g(p)=p^{2}-1,g(p^{k})=p^{2k-2}(p^{2}-1)$ ，然后对 $f_{n}(k)$ 使用数论分块计算，设 $l,r$ 为每次数论分块的边界值，令 $sum=(S(r)-S(l-1))$

$f_{n}(k)=\sum_{T=1}^{n}\left \lfloor \frac{n}{T}\right \rfloor^{k}sum$

对于 $\sum _{i=2}^{k}f_{n}(i)$

$ans=\sum _{i=2}^{k}\sum_{T=1}^{n}\left \lfloor \frac{n}{T}\right \rfloor^{i}sum$

$=\sum_{T=1}^{n}sum\sum _{i=2}^{k}\left \lfloor \frac{n}{T}\right \rfloor^{i}$

设 $\left \lfloor \frac{n}{T}\right \rfloor=q$ ，讨论 $q=1$ 与 $q\neq 1$ 的情况

$ans=\sum_{T=1}^{n}sum\frac{q^{2}(1-q^{k-1})}{1-q}[q\neq 1]+sum(k-1)[q=1]$

注意k的值极大，求解 $q^{k-1}$ 需要使用欧拉定理进行降幂

不难证明复杂度为 $O(T(n^{\frac{2}{3}}+\sqrt{n}log10^{9}))$

#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;
}