求 answer = ∑ [gcd(x, y) = d] (1 <= x <= a, 1 <= y <= b) .

令a' = a / d, b' = b / d, 化簡(jiǎn)一下得到:

answer = Σ?μ(t)*?a'/t?*?b'/t?

?a'/t?相等的是一段連續(xù)的區(qū)間,??b'/t?同理, 而且數(shù)量是根號(hào)級(jí)別的

所以搞出μ的前綴和然后分塊處理.

----------------------------------------------------------------

#include<bits/stdc++.h>using namespace std;const int maxn = 50009;bool check[maxn];int mu[maxn], prime[maxn], N = 0;void init() {memset(check, false, sizeof check);mu[1] = 1;for(int i = 2; i < maxn; i++) {if(!check[i]) {mu[i] = -1; ? ?prime[N++] = i;}for(int j = 0; j < N && i * prime[j] < maxn; j++) {check[i * prime[j]] = true;if(i % prime[j])? ? ?mu[i * prime[j]] = -mu[i];else {mu[i * prime[j]] = 0;break;}}}for(int i = 1; i < maxn; i++) ? ?mu[i] += mu[i - 1];}void work(int a, int b) {if(a > b) swap(a, b);int ans = 0;for(int L = 1; L <= a; L++) {int R = min(a / (a / L), b / (b / L));ans += (mu[R] - mu[L - 1]) * (a / L) * (b / L);L = R;}printf("%d\n", ans);}int main() {init();int T;cin >> T;while(T--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);work(a / c, b / c);}return 0;}

----------------------------------------------------------------

1101: [POI2007]Zap

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?1599??Solved:?554
[Submit][Status][Discuss]

Description

FGD正在破解一段密碼，他需要回答很多類似的問(wèn)題：對(duì)于給定的整數(shù)a,b和d，有多少正整數(shù)對(duì)x,y，滿足x<=a，y<=b，并且gcd(x,y)=d。作為FGD的同學(xué)，FGD希望得到你的幫助。

Input

第一行包含一個(gè)正整數(shù)n，表示一共有n組詢問(wèn)。（1<=n<= 50000）接下來(lái)n行，每行表示一個(gè)詢問(wèn)，每行三個(gè)正整數(shù)，分別為a,b,d。（1<=d<=a,b<=50000）

Output

對(duì)于每組詢問(wèn)，輸出到輸出文件zap.out一個(gè)正整數(shù)，表示滿足條件的整數(shù)對(duì)數(shù)。

Sample Input

2
4 5 2
6 4 3

Sample Output

3
2

HINT

對(duì)于第一組詢問(wèn)，滿足條件的整數(shù)對(duì)有(2,2)，（2,4），（4，2）。對(duì)于第二組詢問(wèn)，滿足條件的整數(shù)對(duì)有（6,3），（3,3）。

Source

?

轉(zhuǎn)載于:https://www.cnblogs.com/JSZX11556/p/4686674.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1101: [POI2007]Zap( 莫比乌斯反演 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。