题目类型：莫比乌斯反演

传送门：>Here<

题意：求有多少对正整数对\((a,b)\)，满足\(0<a<A\),\(0<b<B\),\(gcd(a,b)=d\)

解题思路

学了莫比乌斯反演，就以这道题来介绍一下莫比乌斯反演的题的应用（下文中，对数表示在规定范围内满足特定条件的数对数量，不是\(log\)的那个对数）

一般碰到有关\(gcd\)的题，一般地，设\(f(n)\)表示\(gcd=n\)的对数，\(F(n)\)表示\(n|gcd\)的对数

根据定义，满足$$F(n)=\sum\limits_{n|d}f(d)$$因此利用公式二进行反演$$f(n)=\sum\limits_{n|d}μ(\dfrac{d}{n})F(d)$$我们之所以要反演，是因为\(F\)比\(f\)更好求。我们根据\(gcd\)的性质，发现其实\(F\)就是要求两数都为\(n\)的倍数的对数。因此根据乘法原理，也就是$$\left \lfloor \dfrac{A}{n} \right \rfloor * \left \lfloor \dfrac{B}{n} \right \rfloor$$。可以\(O(1)\)求得

因此只需要筛完\(μ\)之后直接求\(f(d)\)作为答案即可。复杂度\(O(n)\)

然而\(O(n)\)的复杂度不足以满足题目要求，因此需要数论分块（整除分块）来优化到\(O(\sqrt{n})\)即可。关于整除分块的用法见上一篇。

Code

/*By DennyQi 2018*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define  r  read()

using namespace std;

typedef long long ll;

const int MAXN = 50010;

const int INF = 1061109567;

const int LIM = 50010;

inline int Max(const int a, const int b){ return (a > b) ? a : b; }

inline int Min(const int a, const int b){ return (a < b) ? a : b; }

inline int read(){

    int x = 0; int w = 1; register char c = getchar();

    for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());

    if(c == '-') w = -1, c = getchar();

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;

}

int T,A,B,d,ans,last,R;

int mu[MAXN],b[MAXN],prime[MAXN],sumu[MAXN],tot;

inline void getMobius(){

	mu[1] = 1;

	for(int i = 2; i <= LIM; ++i){

		if(!b[i]){

			prime[++tot] = i;

			mu[i] = -1;

		}

		for(int j = 1; j <= tot; ++j){

			if(i * prime[j] > LIM) break;

			b[i * prime[j]] = 1;

			if(i % prime[j] == 0){

				mu[i * prime[j]] = 0;

				break;

			}

			else{

				mu[i * prime[j]] = -mu[i];

			}

		}

	}

	for(int i = 1; i <= LIM; ++i){

		sumu[i] = sumu[i-1] + mu[i];

	}

}

int main(){

	getMobius();

	T = r;

	while(T--){

		A = r, B = r, d = r;

		ans = 0;

		A /= d, B /= d;

		for(int i = 1, j; i <= Min(A,B); i = j+1){

			j = Min(A/(A/i), B/(B/i));

			ans += (A/i) * (B/i) * (sumu[j] - sumu[i-1]);

		}

		printf("%d\n", ans);

	}

	return 0;

}