BZOJ4916 神犇和蒟蒻（欧拉函数+杜教筛）

时间：2023-11-14 21:27:02

　　第一问是来搞笑的。由欧拉函数的计算公式容易发现φ(i2)=iφ(i)。那么可以发现φ(n2)*id(n)（此处为卷积）=Σd*φ(d)*(n/d)=nΣφ(d)=n2 。这样就有了杜教筛所要求的容易算前缀和的两个函数。一通套路即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

#define ll long long

#define P 1000000007

#define N 1000010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,phi[N],iphi[N],prime[N],cnt,inv6=;

map<int,int> f;

bool flag[N];

inline void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int sumone(int x){return (1ll*x*(x+)>>)%P;}

int sumtwo(int x){return 1ll*x*(x+)%P*(x<<|)%P*inv6%P;}

int work(int x)

{

    if (x<=min(n,N-)) return iphi[x];

    if (f.find(x)!=f.end()) return f[x];

    int s=sumtwo(x);

    for (int i=;i<=x;i++)

    {

        int t=x/(x/i);

        inc(s,P-1ll*(sumone(t)-sumone(i-)+P)*work(x/i)%P);

        i=t;

    }

    f[x]=s;return s;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4916.in","r",stdin);

    freopen("bzoj4916.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();cout<<<<endl;

    flag[]=;phi[]=;

    for (int i=;i<=min(n,N-);i++)

    {

        if (!flag[i]) prime[++cnt]=i,phi[i]=i-;

        for (int j=;j<=cnt&&prime[j]*i<=min(n,N-);j++)

        {

            flag[prime[j]*i]=;

            if (i%prime[j]==) {phi[prime[j]*i]=phi[i]*prime[j];break;}

            phi[prime[j]*i]=phi[i]*(prime[j]-);

        }

    }

    for (int i=;i<=min(n,N-);i++) iphi[i]=1ll*i*phi[i]%P;

    for (int i=;i<=min(n,N-);i++) inc(iphi[i],iphi[i-]);

    cout<<work(n);

    return ;

}

相关文章