1，[POI2007]ZAP-Queries

～～～題面～～～
題解：　首先列出式子：$$ans = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[gcd(i, j) == d]$$
　　　　$$[gcd(i, j) == d] = [gcd(\lfloor{\frac{i}ze8trgl8bvbq}\rfloor,\lfloor{\frac{j}ze8trgl8bvbq}\rfloor) == 1]$$
　　　　所以原式 $$\Rightarrow \quad \sum_{i = 1}^{\lfloor{\frac{n}ze8trgl8bvbq}\rfloor}\sum_{j = 1}^{\lfloor{\frac{m}ze8trgl8bvbq}\rfloor}[gcd(i, j)==1]$$
　　　　$$\Rightarrow \quad \sum_{i = 1}^{n}\sum_{j = 1}^{m}\sum_{d|gcd(i, j)}\mu(d)$$
　　　　因為$\mu(d)$會被統計到當且僅當$d | i \quad and \quad d | j$,即$d | gcd(i, j)$
　　　　那么考慮將滿足條件的i和j兩兩搭配，組成的方案數就是$\mu(d)$會被統計到的次數，
　　　　也就是$\mu(d)$會被統計到$\lfloor{\frac{n}ze8trgl8bvbq}\rfloor\lfloor{\frac{m}ze8trgl8bvbq}\rfloor$次
　　　　$$\Rightarrow \quad ans=\sum_{i=1}^{min(n,m)}{\mu(d)\lfloor{\frac{n}ze8trgl8bvbq}\rfloor\lfloor{\frac{m}ze8trgl8bvbq}\rfloor}$$
　　　　然后觀察到$\lfloor{\frac{n}ze8trgl8bvbq}\rfloor\lfloor{\frac{m}ze8trgl8bvbq}\rfloor$中有很多小段$\lfloor{\frac{n}ze8trgl8bvbq}\rfloor\lfloor{\frac{m}ze8trgl8bvbq}\rfloor$乘積是固定的，也就是$\lfloor{\frac{n}ze8trgl8bvbq}\rfloor$和$\lfloor{\frac{m}ze8trgl8bvbq}\rfloor$同時為一個固定的值，因此我們可以用整數分塊優化

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 55000 5 int t, n, m, d; 6 int prime[AC], mu[AC], sum[AC], tot; 7 bool z[AC]; 8 9 inline int read() 10 { 11 int x = 0;char c = getchar(); 12 while(c > '9' || c < '0') c = getchar(); 13 while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 14 return x; 15 } 16 17 void getprime() 18 { 19 int now; 20 mu[1] = 1; 21 for(R i = 2; i <= 50000; i++) 22 { 23 if(!z[i]) prime[++tot] = i, mu[i] = -1; 24 for(R j = 1; j <= tot; j++) 25 { 26 now = prime[j]; 27 if(now * i > 50000) break; 28 // printf("!!!%d %d\n", now, i); 29 z[now * i] = true; 30 if(!(i % now)) break; 31 mu[i * now] = -mu[i]; 32 } 33 } 34 for(R i = 1; i <= 50000; i++) 35 sum[i] = mu[i] + sum[i - 1]; 36 } 37 38 int ans; 39 40 void work() 41 { 42 int pos; 43 t = read(); 44 for(R i = 1; i <= t; i++) 45 { 46 n = read(), m = read(), d = read(); 47 n /= d, m /= d; 48 int b = min(n, m); 49 ans = 0; 50 for(R j = 1; j <= b; j = pos + 1) 51 { 52 pos = min(n / (n / j), m / (m / j)); 53 ans += (sum[pos] - sum[j-1]) * (n / j) * (m / j); 54 } 55 printf("%d\n", ans); 56 } 57 } 58 59 int main() 60 { 61 // freopen("in.in", "r", stdin); 62 getprime(); 63 work(); 64 // fclose(stdin); 65 return 0; 66 } View Code

?

2,[HAOI2011]Problem b

～～～題面～～～
題解：　這題相比上題多出了兩個限制條件，同時對上下限都有限制，那么此時可以用一個容斥來求。
　　　　設$cal(n,m)$表示滿足$x \le n$和$y \le m$且$gcd(x, y) = d$的點對個數，
　　　　那么$$ans = cal(b, d) - cal(a - 1, d) - cal(b, c - 1) + cal(a - 1, c - 1);$$

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 55000 5 #define LL long long 6 int a, b, c, d, tot, k, t, ans; 7 int prime[AC], mu[AC], sum[AC]; 8 bool z[AC]; 9 10 inline int read() 11 { 12 int x = 0; char c = getchar(); 13 while(c > '9' || c < '0') c = getchar(); 14 while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 15 return x; 16 } 17 18 void pre() 19 { 20 int now; 21 mu[1] = 1; 22 for(R i = 2; i <= 50000; i++) 23 { 24 if(!z[i]) prime[++tot] = i, mu[i] = -1;//質數的mu值肯定都是-1 25 for(R j = 1; j <= tot; j++) 26 { 27 now = prime[j]; 28 if(now * i > 50000) break; 29 z[now * i] = true; 30 if(!(i % now)) break; 31 mu[i * now] = -mu[i];//error這里的mu是由mu[i]得來的啊！！！ 32 } 33 } 34 for(R i = 1; i <= 50000; i++) sum[i] = sum[i - 1] + mu[i]; 35 } 36 37 int cal(int n, int m) 38 { 39 n /= k, m /= k; 40 int b = min(n, m), pos, rnt = 0; 41 for(R i = 1; i <= b; i = pos + 1) 42 { 43 pos = min(n / (n / i), m / (m / i)); 44 rnt += (sum[pos] - sum[i-1]) * (n / i) * (m / i); 45 } 46 return rnt; 47 } 48 //ans = cal(b, d) - cal(a - 1, d) - cal(b, c - 1) + cal(a - 1 , c - 1)，相當于容斥 49 50 void work() 51 { 52 t = read(); 53 for(R i = 1; i <= t; i++) 54 { 55 a = read(), b = read(), c = read(), d = read(), k = read(); 56 ans = cal(b, d) - cal(a - 1, d) - cal(b, c - 1) + cal(a - 1, c - 1); 57 printf("%d\n", ans); 58 } 59 } 60 61 int main() 62 { 63 // freopen("in.in", "r", stdin); 64 pre(); 65 work(); 66 // fclose(stdin); 67 return 0; 68 } View Code

?

轉載于:https://www.cnblogs.com/ww3113306/p/9471558.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的[POI2007]ZAP-Queries [HAOI2011]Problem b 莫比乌斯反演的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。