題目描述

神犇YY虐完數(shù)論后給傻×kAc出了一題給定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)為質(zhì)數(shù)的(x, y)有多少對(duì)kAc這種 傻×必然不會(huì)了，于是向你來請(qǐng)教……多組輸入

輸入

第一行一個(gè)整數(shù)T 表述數(shù)據(jù)組數(shù)接下來T行，每行兩個(gè)正整數(shù)，表示N, M

輸出

T行，每行一個(gè)整數(shù)表示第i組數(shù)據(jù)的結(jié)果

樣例輸入

2
10 10
100 100

樣例輸出

30
2791

---

題解

莫比烏斯反演

設(shè)后面的sigma中的式子為f(k)，那么可以在篩完素?cái)?shù)和mu之后處理出f(i)，根據(jù)粗略素?cái)?shù)個(gè)數(shù)和調(diào)和級(jí)數(shù)，時(shí)間復(fù)雜度大約是O(n)的。

于是轉(zhuǎn)變?yōu)榍?/p>

然后再求f(i)的前綴和，然后分塊處理即可。

#include <cstdio> #include <algorithm> using namespace std; const int n = 10000000; int mu[n + 10] , prime[n + 10] , tot; long long f[n + 10] , sum[n + 10]; bool np[n + 10]; long long cal(int a , int b) {int i , last;long long ans = 0;for(i = 1 ; i <= a && i <= b ; i = last + 1) last = min(a / (a / i) , b / (b / i)) , ans += (sum[last] - sum[i - 1]) * (a / i) * (b / i);return ans; } int main() {int i , j , T , a , b;mu[1] = 1;for(i = 2 ; i <= n ; i ++ ){if(!np[i]) mu[i] = -1 , prime[++tot] = i;for(j = 1 ; j <= tot && i * prime[j] <= n ; j ++ ){np[i * prime[j]] = 1;if(i % prime[j] == 0){mu[i * prime[j]] = 0;break;}else mu[i * prime[j]] = -mu[i];}}for(i = 1 ; i <= tot ; i ++ )for(j = 1 ; j * prime[i] <= n ; j ++ )f[j * prime[i]] += mu[j];for(i = 1 ; i <= n ; i ++ ) sum[i] = sum[i - 1] + f[i];scanf("%d" , &T);while(T -- ) scanf("%d%d" , &a , &b) , printf("%lld\n" , cal(a , b));return 0; }

?

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

總結(jié)

以上是生活随笔為你收集整理的【bzoj2820】YY的GCD 莫比乌斯反演的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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