51Nod 1244 莫比乌斯函数之和

Description

求\(\sum_{i=a}^b\mu(i),1\leqslant l\leqslant r\leqslant 10^{10}\)

Solution

杜教筛..贴代码..

Code

#include 
using namespace std;

typedef long long ll;
const int N = 2000500;
const ll p = 1000000007;

int pr[N],cp,b[N],mu[N],smu[N];

void pre(int n) {
	mu[1]=1;
	for(int i=2;i<=n;i++) {
		if(!b[i]) pr[++cp]=i,mu[i]=-1;
		for(int j=1;j<=cp && i*pr[j]<=n;j++) {
			b[i*pr[j]]=1;
			if(i%pr[j]) mu[i*pr[j]]=-mu[i];
			else break;
		}
	}for(int i=1;i<=n;i++) smu[i]=(smu[i-1]+mu[i]);
//	for(int i=1;i<=10;i++) cout< mp;
ll S(ll n) {
	if(n<=2000000) return smu[n];
	if(mp.count(n)) return mp[n];
	ll fn=1;
	for(ll i=2,j;i<=n;i=j+1) {
		j=n/(n/i);
//		cout<