首页 > 代码库 > 51nod 1244 莫比乌斯函数之和

51nod 1244 莫比乌斯函数之和

题目链接:51nod 1244 莫比乌斯函数之和

推荐学习博客:http://blog.csdn.net/skywalkert/article/details/50500009 然后,这题解法里面提到了,我就不打公式了,,,好好看大神的博客唉orz

用筛法预处理前N^(2/3)项,后面的记忆化搜索解决。还不会哈希唉,先用map了。

今晚自学感觉晕晕的,有空我还是要去练练其他题orz

技术分享
 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 using namespace std;
 7 #define CLR(a,b) memset((a),(b),sizeof((a)))
 8 typedef long long ll;
 9 const int N = 6000000;
10 bool check[N+10];
11 int prime[N+10];
12 int mu[N+10];
13 ll mu_sum[N+10];
14 void Moblus(){
15     CLR(check, false);
16     mu[1] = 1;
17     int tot = 0;
18     for(int i = 2; i <= N; i++){
19         if( !check[i] ){
20             prime[tot++] = i;
21             mu[i] = -1;
22         }
23         for(int j = 0; j < tot && i*prime[j] <= N; j++){
24             check[i * prime[j]] = true;
25             if( i % prime[j] == 0){
26                 mu[i * prime[j]] = 0;
27                 break;
28             }
29             else
30                 mu[i * prime[j]] = -mu[i];
31         }
32     }
33     for(int i = 1; i <= N; ++i)
34         mu_sum[i] = mu_sum[i-1] + mu[i];
35 }
36 map<ll,ll> mp;
37 ll Mertens(ll n){
38     if(n <= N) return mu_sum[n];
39     if(mp.count(n)) return mp[n];
40     ll ans = 1, ed;
41     for(ll i = 2; i <= n; i = ed+1){
42         ed = n/(n/i);
43         ans -= (ed - i + 1)*Mertens(n/i);
44     }
45     return mp[n] = ans;
46 }
47 int main(){
48     Moblus();
49     ll a, b;
50     scanf("%lld%lld", &a, &b);
51     printf("%lld\n", Mertens(b) - Mertens(a-1));
52     return 0;
53 }
View Code

 

51nod 1244 莫比乌斯函数之和