题目描述
神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种
傻×必然不会了，于是向你来请教……多组输入
输入
第一行一个整数T 表述数据组数接下来T行，每行两个正整数，表示N, M
输出
T行，每行一个整数表示第i组数据的结果
样例输入
2 10 10 100 100
样例输出
30 2791
题解
莫比乌斯反演
设后面的sigma中的式子为f(k)，那么可以在筛完素数和mu之后处理出f(i)，根据粗略素数个数和调和级数，时间复杂度大约是O(n)的。
于是转变为求
然后再求f(i)的前缀和，然后分块处理即可。
#include#include 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;}