当前位置:网站首页>Du Jiaosha & min_ 25 screen learning notes

Du Jiaosha & min_ 25 screen learning notes

2020-12-24 23:27:31 RingweEH

0 - In front of

Mobius inversion

See Link , Here are some formulas .

Dirichlet Convolution :

\[(f*g)(x)=\sum_{d|x}f(d)g(\frac{x}{d}) \]

Mobius inversion :

\[f=g*1=>g=f*\mu\\ f(x)=\sum_{d|x}g(d)=>g(x)=\sum_{d|x}f(d)\times \mu(\frac{x}{d}). \]

Euler function

nature :\(\sum_{d|n} \varphi(d)=n\)

Expressed as Dirichlet Convolution In the form of :\(\varphi*I=id\) .

On volume \(\mu\) have to

\[\varphi*I=id\\ =>\varphi*I*\mu=id*\mu\\ =>\varphi * \epsilon=id*\mu \]

So there is

\[\varphi(n)=\sum_{d|n}\mu(d)\cdot\frac{n}{d} \]

so

\[\frac{\varphi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d} \]

1 - Dujiao sieve

Method

purpose : Computes the product function prefix and... With less than linear complexity , Computation :\(\sum_{i=1}^n f(i)\) .

deduction :

Construct two product functions \(h,g\) , bring \(h=f*g\) .

remember \(S(n)=\sum_{i=1}^n f(i)\) , So there are

\[\begin{aligned} \sum_{i=1}^nh(i) &=\sum_{i=1}^n\sum_{d|i}g(d)\cdot f(\frac{i}{d})\\\\ &=\sum_{d=1}^ng(d)\cdot \sum_{i=1}^{\lfloor n/d\rfloor} f(i)\\\\ &=\sum_{d=1}^ng(d)\cdot S(\lfloor \frac{n}{d}\rfloor )\\\\ &=g(1)\cdot S(n)+\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)\\\\ g(1)S(n)&=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)\cdot S(\lfloor \frac{n}{d}\rfloor ) \end{aligned} \]

So the key is to find one that is easy to get \(h\) . After obtaining, it is good to divide the following into blocks , Complexity \(\mathcal{O}(n^{\frac 23})\) .

About complexity (@George1123)

Direct recursive truth \(\Theta(n^{\frac{3}{4}})\)

\[\begin{split} T(n)=&\sqrt n+\sum\limits_{i=2}^{\sqrt n}\left(T(i)\cdot T(\lfloor\frac{n}{i}\rfloor)\right)\\ \ge&\sqrt n+\sum\limits_{i=2}^{\sqrt n}\left(\sqrt i\cdot \sqrt{\lfloor\frac{n}{i}\rfloor)}\right)\\ \ge&\sqrt n+\sum\limits_{i=2}^{\sqrt n}2\sqrt{\sqrt n}\\ =&n^{\frac{3}{4}}\\ \end{split} \]

Before finding out the linear sieve \(n^{\frac23}\) individual , And then I'll teach you to sift , yes \(\Theta(n^{\frac{2}{3}})\) .

\[\begin{split} T(n)=&m+\sum\limits_{i=2}^{\lfloor\frac nm\rfloor}\sqrt{\lfloor\frac ni\rfloor}\\ =&m+\frac{n}{\sqrt m}\\ \ge&2n^{\frac{2}{3}}(=: \operatorname{while} m=n^{\frac{2}{3}})\\ \end{split} \]

Example

Mobius function

seek

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

because \(\mu*I=\epsilon\) , therefore Make \(I=>g,\epsilon=>h\) , According to the above formula

\[g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)\cdot S(\lfloor \frac{n}{d}\rfloor ) \]

Yes

\[\begin{aligned} 1\times S(n)&=\sum_{i=1}^n\epsilon(i)-\sum_{d=2}^nS(\lfloor \frac{n}{d}\rfloor )\\\\ S(n) &= 1-\sum_{d=2}^nS(\lfloor \frac nd\rfloor) \end{aligned} \]

Euler function

seek

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

because \(\varphi *I=ID\) , therefore

\[\begin{aligned} S(n) &=\sum_{i=1}^n i-\sum_{d=2}^n S(\lfloor \frac{n}{d}\rfloor)\\\\ &=\frac{n(n+1)}{2}-\sum_{d=2}^nS(\lfloor \frac{n}{d}\rfloor) \end{aligned} \]

? function

seek

\[S(n)=\sum_{i=1}^ni\cdot \varphi(i) \]

consider Dirichlet The form of convolution :

\[\sum_{d|n}(d\cdot \varphi(d))\cdot g(\frac{n}{d}) \]

Make \(ID=>g\) , Yes

\[\sum_{d|n}(d\cdot \varphi(d))\cdot \frac{n}{d}=\sum_{d|n}n\cdot \varphi(d)=n\sum_{d|n}\varphi(d)=n^2 \]

So there is

\[S(n)=\sum_{i=1}^ni^2-\sum_{d=2}^nd\cdot S(\lfloor \frac{n}{d}\rfloor) \]

?? function

seek

\[\sum_{i=1}^n\mu(i)i^2 \]

Make \(g(i)=i^2\) , Yes

\[g*f(n)=\sum_{d|n}\mu(d)d^2\cdot\Big(\frac{n}{d}\Big)^2=\sum_{d|n}\mu(d)=[n=1] \]

therefore

\[S(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^nd^2\cdot S(\lfloor \frac{n}{d}\rfloor )=1-\sum_{d=2^n}d^2\cdot S(\lfloor \frac{n}{d}\rfloor) \]

Code

Big constant players play Templates

//Author: RingweEH
const int N=5e5+10;
int pri[N],tot=0,n;
ll mu[N],phi[N];
bool is[N];

void Sieve()
{
    mu[1]=phi[1]=1; is[1]=1;
    for ( int i=2; i<=N-10; i++ )
    {
        if ( !is[i] ) { pri[++tot]=i,mu[i]=-1,phi[i]=i-1; }
        for ( int j=1; j<=tot && (i*pri[j]<=(N-10)); j++ )
        {
            is[i*pri[j]]=1;
            if ( i%pri[j]==0 ) { mu[i*pri[j]]=0,phi[i*pri[j]]=phi[i]*pri[j]; break; }
            mu[i*pri[j]]=-mu[i]; phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
    for ( int i=2; i<=(N-10); i++ )
        mu[i]+=mu[i-1],phi[i]+=phi[i-1];
}

map<int,ll> mp_mu,mp_phi;

ll Sieve_Phi( int n )
{
    if ( n<=N-10 ) return phi[n];
    if ( mp_phi[n] ) return mp_phi[n];
    ll _res=0;
    for ( int l=2,r; l<=n; l=r+1 )
    {
        r=n/(n/l); _res+=(r-l+1)*Sieve_Phi(n/l);
        if ( r>=2147483647 ) break;
    }
    ll res=(ull)n*(n+1ll)/2ll-_res;
    mp_phi[n]=res; return res;
}

ll Sieve_Mu( int n )
{
    if ( n<=N-10 ) return mu[n];
    if ( mp_mu[n] ) return mp_mu[n];
    ll res=1;
    for ( int l=2,r; l<=n; l=r+1 )
    {
        r=n/(n/l); res-=(r-l+1)*Sieve_Mu(n/l);
        if ( r>=2147483647 ) break;
    }
    return mp_mu[n]=res;
}

int main()
{
    Sieve();
    int T=read();
    while ( T-- )
    {
        int n=read();
        printf("%lld %lld\n",Sieve_Phi(n),Sieve_Mu(n) );
    }
    return 0;
}

Example

The mathematical problem of cancer

seek

\[\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j)\right)\bmod p \]

\(1\le n\le 10^{10},5\times10^{8}\le p\le 1.1\times 10^{9}\) .

Solution

It's hard to use five level titles

\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j) &=\sum_{d=1}^n d^3\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor n/d\rfloor} ij[\gcd(i,j)=1]\\\\ &=\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor n/d\rfloor}ij\sum_{k|d}\mu(k)\\\\ Make S(n)=\frac{n*(n+1)}2,&=\sum_{d=1}^nd^3\sum_{k|d}\mu(k)k^2S(\lfloor \frac{n}{dk}\rfloor)^2\\\\ &=\sum_{d=1}^nd^3\sum_{k=1}^{\lfloor n/d\rfloor}\mu(k)k^2S(\lfloor \frac{n}{dk}\rfloor)^2 \end{aligned} \]

use \(T=dk\) Replace , obtain :

\[\begin{aligned} \sum_{d=1}^nd^3\sum_{k=1}^{\lfloor n/d\rfloor}\mu(k)k^2S(\lfloor \frac{n}{dk}\rfloor)^2 &=\sum_{d=1}^nd^3\sum_{k=1}^{\lfloor n/d\rfloor}\mu(k)k^2S(\lfloor \frac{n}{T}\rfloor)^2\\\\ &=\sum_{T=1}^nS(\lfloor \frac nT\rfloor)^2\sum_{d|T}d^3\mu\Big(\frac{T}{d}\Big)\Big(\frac{T}{d}\Big)^2\\\\ &=\sum_{T=1}^nS(\lfloor \frac nT\rfloor)^2T^2\sum_{d|T}\mu\Big(\frac{T}{d}\Big)\cdot d\\\\ \end{aligned} \]

According to the prepositional knowledge in Murphy , Yes

\[\varphi(x)=(\mu*ID)(x)=\sum\limits_{d|x}d\cdot\mu(\frac xd)\\\\ \]

therefore :

\[=\sum_{T=1}^nS(\lfloor \frac{n}{T}\rfloor )^2T^2\varphi(T)\\\\ \]

Then you can have a good time . Take out the template for observation :

\[g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)\cdot S(\lfloor \frac{n}{d}\rfloor )( Dujiao sieve )\\\\ (f*g)(x)=\sum_{d|x}f(d)g(\frac{x}{d})(Dirichlet Convolution )\\\\ \varphi*1=ID( and \varphi The antecedent of the equation ) \]

Make \(sum(n)=\sum_{i=1}^ni^2\varphi(i)\) , Obviously we need to put \(sum(n)\) In this \(i^2\) Eliminate . Look at convolution , Consideration order \(g(n)=n^2\) .

So there is :

\[(f*g)(n)=\sum_{d|n}d^2\varphi(d)\Big(\frac{n}{d}\Big)^2=n^2\sum_{d|n}\varphi(d) \]

And then press the last formula :

\[(f*g)(n)=n^3. \]

Then there is :

\[sum(n)=\sum_{i=1}^ni^3-\sum_{d=2}^nd^2sum(\lfloor \frac{n}{d}\rfloor)\\\\ \]

For the original :

\[\sum_{T=1}^nS(\lfloor \frac{n}{T}\rfloor )^2T^2\varphi(T)\\\\ \]

Then we can solve the problem .

Code
//Author: RingweEH
const int N=5e6+10;
int pri[N],tot=0,phi[N],sum[N],Mod;
ll n,inv6,inv2;
bool is[N];

int power( int a,int b )
{
	int res=1;
	for ( ; b; b>>=1,a=1ll*a*a%Mod )
		if ( b&1 ) res=1ll*res*a%Mod;
	return res;
}

void Sieve()
{
	phi[1]=1; is[1]=1;
	for ( int i=2; i<=(N-10); i++ )
	{
		if ( !is[i] ) pri[++tot]=i,phi[i]=i-1;
		for ( int j=1; j<=tot && (i*pri[j]<=(N-10)); j++ )
		{
			int pos=i*pri[j]; is[pos]=1;
			if ( i%pri[j]==0 ) { phi[pos]=1ll*phi[i]*pri[j]%Mod; break; }
			else phi[pos]=1ll*phi[i]*phi[pri[j]]%Mod;
		}
	}
	for ( int i=1; i<=(N-10); i++ )
		sum[i]=(1ll*i*i%Mod*phi[i]%Mod+sum[i-1])%Mod;
}

int pow1( ll x )
{
	x%=Mod; int res=x*(x+1)%Mod*inv2%Mod;
	return res;
}

int pow2( ll x )
{
	x%=Mod; int res=1ll*x*(x+1)%Mod*(2*x+1)%Mod*inv6%Mod;
	return res;
}

int pow3( ll x )
{
	int res=pow1(x); res=1ll*res*res%Mod;
	return res;
}

unordered_map<ll,int> mp;
int Sieve_Mu( ll x )
{
	if ( x<=(N-10) ) return sum[x];
	if ( mp[x] ) return mp[x];
	int res=pow3(x);
	for ( ll l=2,r; l<=x; l=r+1 )
	{
		r=x/(x/l); res=(res-1ll*(pow2(r)-pow2(l-1))*Sieve_Mu(x/l)%Mod)%Mod;
	}
	mp[x]=(res+Mod)%Mod; return mp[x];
}

void init()
{
	Sieve(); inv2=power( 2ll,Mod-2 ); inv6=power( 6ll,Mod-2 );
}

int main()
{
	Mod=read(),n=read(); init();

	ll ans=0;
	for ( ll l=1,r; l<=n; l=r+1 )
	{
		r=n/(n/l); ans=(ans+1ll*(Sieve_Mu(r)-Sieve_Mu(l-1))*pow3(n/l)%Mod)%Mod;
	}

	printf( "%lld\n",(ans+Mod)%Mod );

	return 0;
}

The beauty of circulation and Min_25 The sieve is still cooing (

版权声明
本文为[RingweEH]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201224222455508m.html

随机推荐