数论

杜教筛

YEs

Posted by JU on November 21, 2018

一些函数

\[\epsilon(n)=[n=1],I(n)=1,id(n)=n\] \[\mu * I = \epsilon\] \[\varphi*I=id\] \[\mu*id=\varphi\] \[\sum_{d|n}\mu(d)=[n==1]\] \[\sum_{d|n}\varphi(d)=n\] \[\varphi(n^2)=n\varphi(n)\]

杜教筛

要求

\[S(n)=\sum_{i=1}^{n}f(i)\]

关键是找到一个 $ g $
再找一个 $ h=f*g $

而且它们的前缀和可以快速计算
于是这个东西

\[g(1)S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)S(\frac{n}{i})\]

在预处理（线性筛）后就可以在 $ O(n^\frac{2}{3}) $ 的时间内计算辣

Luogu3768

\(\sum_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i,j)\)

\[\sum_{i=1}^{n}i\sum_{j=1}^{n}j\sum_{d|\gcd(i,j)}\phi(d)\] \[ans=\sum_{d=1}^{n}\phi(d)d^2\lfloor\frac{(n)(n+1)}{2}\rfloor^2\] \[h(n)=n^3,f(n)=\phi(n)n^2,g(n)=n^2\] \[S(n)=\sum_{i=1}^{n}f(i),G(n)=\sum_{i=1}^{n}g(i)=\frac{n(n+1)(2n+1)}{6},H(n)=\sum_{i=1}^{n}h(i)=\frac{n^2(n+1)^2}{4}\] \[\sum_{i=1}^{n}h(i)=\sum_{i=1}^{n}\sum_{d|i}g(d)f(\frac{i}{d})\] \[=\sum_{d=1}^{n}g(d)\sum_{i=1}^{n/d}f(i)\] \[=\sum_{d=1}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)\] \[H(n)=g(1)S(n)+\sum_{d=2}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)\] \[S(n)=H(n)-\sum_{d=2}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)\] 
#include <bits/stdc++.h>
#define pr(p) printf("%lld\n",p)
const int oo=2147483640;
const int N=10010000;
using namespace std;
typedef long long LL;
inline void sc (LL &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
LL mod;
LL ksm (LL a,LL b)
{
    LL ans=1;
    while (b)
    {
        if (b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
const LL fw=1e7;
LL pri[N],phi[N],inv; bool vis[N];
void getphi ()
{
    inv=ksm (6,mod-2);
    phi[1]=1;
    for (LL i=2; i<=fw; i++)
    {
        if (!vis[i]) pri[++pri[0]]=i,phi[i]=i-1;
        for (LL j=1; j<=pri[0]; j++)
        {
            LL k=i*pri[j]; if (k> fw) break;
            vis[k]=1;
            if (i%pri[j]==0) { phi[k]=phi[i]*pri[j]; break; }
            phi[k]=phi[i]*phi[pri[j]];
        }
    }
    for (LL i=2; i<=fw; i++)
        phi[i]=(phi[i]*i%mod*i%mod+phi[i-1])%mod;
}
LL g(LL n) { return n%mod*n%mod; }
LL G(LL n) { n%=mod; return n*(n+1)%mod*(2*n+1)%mod*inv%mod; }
LL H(LL n) { n%=mod; return (n*(n+1)/2%mod)*(n*(n+1)/2%mod); }
map <LL,LL> p;
LL S(LL n)
{
    if (n<=fw) return phi[n];
    if (p.find (n)!=p.end ()) return p[n];
    LL ans=H(n);
    for (LL d=2; d<=n; )
    {
        LL nx=n/(n/d);
        ans=(ans- (G(nx)-G(d-1)+mod)%mod * S(n/d)%mod +mod)%mod;
        d=nx+1;
    }
    return p[n]=ans;
}
int main()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    LL n,ans=0; sc(mod),sc(n);
    getphi ();
    for (LL d=1; d<=n; )
    {
        LL nx=n/(n/d);
        ans=(ans+ (S(nx)-S(d-1)+mod)%mod * (H(n/d)%mod) %mod)%mod;
        d=nx+1;
    }
    pr(ans);
    return 0;
}
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：杜教筛”
CATALOG
    FRIENDS