复习一下杜教筛(所有除法向下取整)

 

公式：

 

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

 

应用时一定要满足 $\sum_{i=1}^{n}(f*g)(i)$ 要能够快速求出,且 $f,g$ 都为积性函数.

 

其中 $(f*g)(i)=\sum_{d|i}{f(d)g(\frac{i}{d})}$

 

就是 $f,g$ 的迪利克雷卷积

 

常见的变换： (证明就不给了)

 

一些定义： $I(x)=1,id(x)=x,\epsilon(x)=[x==1]$

 

(1) $(\mu*I)(i)=\epsilon(i)$

 

(2) $(\varphi*I)(i)=id(i)$

 

(3) $(id*\mu)(i)=\varphi(i)$           

#include
     
      #define maxn 10000004#define  ll long long #define M 1000002  using namespace std;void setIO(string s){	string in=s+".in"; 	freopen(in.c_str(),"r",stdin); }int cnt; bool vis[maxn]; int prime[maxn], phi[maxn]; ll sumv[maxn]; ll Sum(ll n) { return (n * (n + 1)) / 2;  }inline void Init(){ 	int i,j;	phi[1]=1; 	for(i=2;i<=M;++i)	{		if(!vis[i]) prime[++cnt]=i, phi[i]=i-1; 		for(j=1;j<=cnt&&1ll*prime[j]*i<=M;++j)		{			vis[prime[j]*i]=1; 			if(i%prime[j]==0) 			{				phi[i*prime[j]]=phi[i]*prime[j]; 				break; 			}			phi[i*prime[j]]=phi[i]*(prime[j]-1); 		}	} 	for(i=1;i<=M;++i) sumv[i]=sumv[i-1]+1ll*phi[i]; }map
      
       sumphi; ll get(int n){	if(n<=M) return 1ll*sumv[n]; 	if(sumphi[n]) return sumphi[n]; 	ll re=1ll*Sum(n); 	int i,j; 	for(i=2;i<=n;i=j+1)	{		j=n/(n/i); 		re -= 1ll*(j-i+1) * 1ll*get(n/i); 	}	return re; }int main(){	// setIO("input"); 	Init();  	int n; 	scanf("%d",&n);  	printf("%lld\n",get(n)); 	return 0; }