Tag: 杜教筛

首先安利两篇Blog：
http://blog.csdn.net/skywalkert/article/details/50500009
http://www.cnblogs.com/joyouth/p/5517734.html

自己对于杜教筛的理解就是下面这个式子：
\(\left\{ {\begin{array}{*{20}{l}}
{f(n) = \sum\limits_{i = 1}^n {\varphi (i)} }\\
{(\varphi \times I)(x) = id}\\
{g(n) = \sum\limits_{i = 1}^n {id(i)} }
\end{array}} \right. \Rightarrow f(n) = g(n) – \sum\limits_{i = {\rm{2}}}^n {f(\frac{n}{i})} \)

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5608

这题，看一眼体面就应该知道是杜教筛吧？
唯一的问题就是求\(\sum\limits_{i = 1}^n {{i^2}} \)
然后就不会了，去问问数竞的大爷，被告知：\(\sum\limits_{i = 1}^n {{i^2}} = \frac{{n \cdot (n + 1) \cdot (2n + 1)}}{6}\)是一个基本公式

至于证明，貌似最清真的还是数学归纳法吧：
设i=1,k=2,不难得出此时原式成立
令k’=k+1则有：\(\sum\limits_{i = 1}^{k’} {{i^2} = \sum\limits_{i = 1}^k {{i^2} + {{(k + 1)}^2} = \frac{{(k + 1) \cdot (k + 2) \cdot (2k + 3)}}{6} = \frac{{k’ \cdot (k’ + 1) \cdot (2k’ + 1)}}{6}} } \)
即命题对于\(\forall k\)都成立

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3944

好像没有什么特别的
但讲道理，下面是map，上面是unordered_map

讲道理啊！这™复杂度都不一样啊！

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000+9;
const int MX = 5000000; 

int mu[N],cnt,pri[N];
bool vis[N]; LL phi[N];
map<int,int> MU;
map<int,LL> PHI;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void prework(){
	mu[1] = phi[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!vis[i]) pri[++cnt] = i, mu[i] = -1, phi[i] = i-1;
		for (int j=1,w;j<=cnt && pri[j]*i<=MX;j++) {
			vis[i*pri[j]] = 1; w = pri[j]*i;
			if (i%pri[j]) mu[w] = -mu[i], phi[w] = phi[i]*(pri[j]-1);
			else {phi[w] = phi[i]*pri[j]; break;}
		}
	} 
	for (int i=1;i<=MX;i++) mu[i] += mu[i-1], phi[i] += phi[i-1];
}

inline int solve_mu(int w) {
	if (w <= MX) return mu[w];
	else if (MU[w]) return MU[w];
	else {
		int ret = 1;
		for (LL i=2,tmp;i<=w;i=tmp+1) {
			tmp = w / (w / i);
			ret -= solve_mu(w/tmp)*(tmp-i+1);
		} MU[w] = ret; return ret;
	}
}

int LL solve_phi(int w) {
    if (w <= MX) return phi[w];
    else if (PHI[w]) return PHI[w];
    else {
        LL ret = w * ((LL)w+1) / 2;
        for (LL i=2,tmp;i<=w;i=tmp+1) {
            tmp = w / (w/i); 
            ret -= solve_phi(w/tmp)*(tmp-i+1);
        } PHI[w] = ret; return ret;
    } 
}

int main(){
	prework(); 
	for (int t=read(),w;t;t--) w = read(), 
		printf("%lld %d\n",solve_phi(w),solve_mu(w));
	return 0;
}

题目传送门：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1244

这个题目，貌似和【51NOD_1239】欧拉函数之和基本一样？

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000+9;
const int MX = 5000000; 

int mu[N],cnt,pri[N];
bool vis[N]; 
unordered_map<LL,LL> M;

inline int prework(){
	mu[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!vis[i]) pri[++cnt] = i, mu[i] = -1;
		for (int j=1;j<=cnt && pri[j]*i<=MX;j++) {
			vis[i*pri[j]] = 1;
			if (i%pri[j]) mu[i*pri[j]] = -mu[i];
			else break;
		}
	} 
	for (int i=1;i<=MX;i++) mu[i] += mu[i-1];
}

inline LL solve(LL w) {
	if (w <= MX) return mu[w];
	else if (M[w]) return M[w];
	else {
		LL ret = 1;
		for (LL i=2,tmp;i<=w;i=tmp+1) {
			tmp = w / (w / i);
			ret -= solve(w/tmp)*(tmp-i+1);
		} M[w] = ret; return ret;
	}
}

int main(){
	prework(); LL a,b; cin>>a>>b;
	printf("%d\n",solve(b)-solve(a-1));
	return 0;
}

题目传送门：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1239

传说中的杜教筛！虽然网上式子很多了，但还是推一推吧！
总体思路：
\(\left\{ {\begin{array}{*{20}{l}}
{f(n) = \sum\limits_{i = 1}^n {\varphi (i)} }\\
{(\varphi \times I)(x) = id}\\
{g(n) = \sum\limits_{i = 1}^n {id(i)} }
\end{array}} \right. \Rightarrow f(n) = g(n) – \sum\limits_{i = {\rm{2}}}^n {f(\frac{n}{i})} \)

至于杜教筛的顺逆推问题，感觉只能凑
不过想一想，能凑的也不过mu，phi这些

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int REV = 500000004;
const int MX = 5000000;
const int N = MX + 9;

unordered_map<LL,int> M;
int phi[N],pri[N],tot;
bool vis[N];

inline LL read(){
	char c=getchar(); LL ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline void prework(){
	phi[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!vis[i]) pri[++tot] = i, phi[i] = i - 1;
		for (int j=1;j<=tot && pri[j]*i<=MX;j++) {
			vis[pri[j]*i] = 1;
			if (i%pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1);
			else {phi[i*pri[j]] = phi[i]*pri[j]; break;}
		}
	}for (int i=1;i<=MX;i++) phi[i] += phi[i-1], phi[i] %= MOD; 	
}

int solve(LL w) {
	if (w <= MX) return phi[w];
	else if (M[w]) return M[w];
	else {
		int ret = ((w%MOD)*((w+1)%MOD)%MOD)*REV%MOD;
		for (LL i=2,tmp;i<=w;i=tmp+1) {
			tmp = w / (w/i); ret %= MOD;
			ret -= (LL)solve(w/tmp)*(tmp-i+1) % MOD;
		} ((ret%=MOD)+=MOD)%=MOD; M[w] = ret; return ret;
	} 
}

int main(){
	prework(); 
	printf("%d\n",solve(read()));
	return 0;
}