莫比乌斯函数之和 51Nod

莫比乌斯函数之和

题意：
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=1e7+5;
 5 int mu[maxn], pri[maxn];
 6 map<ll,int> mp;
 7 void init(){
 8     mu[1] = 1;
 9     int cnt = 0;
10     for(int i = 2; i < maxn; i++) {
11         if(!pri[i]) {
12             pri[cnt++] = i;
13             mu[i] = -1;
14         }
15         for(int j = 0; j < cnt; j++) {
16             int t = pri[j]*i;
17             if(t>=maxn) break;
18             pri[t] = 1;
19             if(i % pri[j] == 0) {
20                 mu[t] = 0;
21                 break;
22             }else {
23                 mu[t] = -mu[i];
24             }
25         }
26         mu[i] += mu[i-1];
27     }
28 }
29 int solve(ll a) {
30     int res = 1;
31     ll r=2, l=2;
32     if(a < maxn) return mu[a];
33     if(mp[a]) return mp[a];
34     while(l <= a){
35         res -= solve(a/r)*(r-l+1);
36         if(r==a) break;
37         l = r+1;
38         r = a/(a/l);
39     }
40     return mp[a] = res;
41 }
42 
43 int main() {
44     init();
45     ll a, b;
46     while(scanf("%lld %lld", &a, &b)!=EOF) {
47         printf("%d
", solve(b) - solve(a-1));
48     }
49 }
View Code