【51NOD 1244】莫比乌斯函数之和

Qizy 数论, 杜教筛, 解题报告

题目传送门：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;
}

15 thoughts to “【51NOD 1244】莫比乌斯函数之和”

  5. 812188 866521Its difficult to get knowledgeable individuals with this subject, but the truth is could be seen as do you know what you are referring to! Thanks 249013

    Reply

  6. 459587 740102Im agitated all these post directories. It positive would be good to have every article directory that instantly accepts articles. 950536

    Reply

  15. I just could not leave your web site prior to suggesting that I really enjoyed the usual information a person provide to your guests? Is going to be back incessantly in order to inspect new posts

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *