题意
求a~b的莫比乌斯函数和，$a,b<=10^{10}$
分析
杜教筛+hash+记忆化
求$S(n) = \sum\limits_{i=1}^{n}μ(i)$
对于莫比乌斯函数有$\sum\limits_{d|i}μ(d)=[i=1]$ 所以$S(n) = \sum\limits_{i=1}^{n}\sum\limits_{d|i}μ(d)-\sum\limits_{i=1}^{n}\sum\limits_{d|i,d≠i}μ(d)$ $=1-\sum\limits_{i=1}^{n}\sum\limits_{d|i,d≠1}μ(\lfloor\frac{i}{d}\rfloor)$ $=1-\sum\limits_{i=2}^{n}\sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor}μ(d)$ $=1-\sum\limits_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor)$
code
1 #include2 #include 3 #include 4 5 using namespace std; 6 const int N = 5000000; 7 const int mod = 1000007; 8 typedef long long LL; 9 10 int prime[N+10],mu[N+10],tot,cnt;11 bool noprime[N+10];12 int h[mod],nxt[mod];13 LL v[mod],d[mod];14 15 void getmu() {16 mu[1] = 1;17 for (int i=2; i<=N; ++i) {18 if (!noprime[i]) prime[++tot] = i,mu[i] = -1;19 for (int j=1; j<=tot&&i*prime[j]<=N; ++j) {20 noprime[i*prime[j]] = true;21 if (i % prime[j]==0) {mu[i*prime[j]] = 0;break;}22 mu[i * prime[j]] = -mu[i];23 }24 }25 for (int i=1; i<=N; ++i) mu[i] += mu[i-1];26 }27 void addhash(LL x,LL y) {28 int p = x % mod;29 d[++cnt] = x;v[cnt] = y;nxt[cnt] = h[p];h[p] = cnt;30 }31 int gethash(LL x) {32 int p = h[x % mod];33 while (p!=-1 && d[p]!=x) p=nxt[p];34 return p;35 }36 LL Calc(LL x) {37 if (x <= N) return (LL)mu[x];38 int p = gethash(x);39 if (p != -1) return v[p];40 LL l=2,r,ret = 1;41 while (l <= x) {42 r = x / (x / l);43 ret -= 1ll * (r - l + 1) * Calc(x / l);44 l = r + 1;45 }46 addhash(x,ret);47 return ret;48 }49 int main () {50 memset(h,-1,sizeof(h));51 memset(nxt,-1,sizeof(nxt));52 LL a,b;53 getmu();54 cin >> a >> b;55 cout << Calc(b) - Calc(a-1);56 return 0;57 }