题目链接：传送门

Description

对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。 数据组数<=50000, a, b <= 50000

Sample Input

2 4 5 2 6 4 3

Sample Output

3 2

Solution

第一道这种数论题

我们假设n<=m，则有

∑i=1n∑j=1m[gcd(i,j)==d]\sum_{i=1}^n \sum_{j=1}^m [gcd(i, j) == d] =∑i=1⌊nd⌋∑j=1⌊md⌋[gcd(i,j)==1]=\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor } [gcd(i, j) == 1]

=∑i=1⌊nd⌋∑j=1⌊md⌋∑g∣i,jnμ(g)=\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{g|i, j}^n \mu(g)

=∑g=1nμ(g)⌊ndg⌋⌊mdg⌋=\sum_{g=1}^n \mu(g) \lfloor \frac{n}{dg} \rfloor \lfloor \frac{m}{dg} \rfloor 然后就能将μ求个前缀和，然后用整除分块来做了

整除分块就是我们可以发现像⌊ni⌋\lfloor \frac{n}{i}\rfloor这样的式子的取值只有N\sqrt N种，而某一段连续的i的区间对应的是同一个值。

我们考虑，如果某一段区间的左端点为d的话，那么所对应的值x就等于⌊nd⌋\lfloor \frac{n}{d}\rfloor。

而区间的右端点的位置显然为⌊nx⌋\lfloor \frac{n}{x}\rfloor，

代入得到此时d=⌊n⌊nd⌋⌋d = \lfloor \frac{n}{\lfloor \frac{n}{d}\rfloor}\rfloor

于是就这样处理即可，复杂度为O(N)O(\sqrt N)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int Maxn = 100000;

int N, M, D;
int Not_Prime[Maxn + 100], Prime[Maxn + 100], Mu[Maxn + 100], cnt;

inline void Init()
{
    Not_Prime[0] = Not_Prime[1] = 1;
    Mu[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Not_Prime[i])
        {
            Prime[++cnt] = i;
            Mu[i] = -1;
        }
        for (int j = 1; j <= cnt && i  * Prime[j] <= Maxn; ++j)
        {
            Not_Prime[i * Prime[j]] = 1;
            if (!(i % Prime[j])) break;
            Mu[i * Prime[j]] = -Mu[i];
        }
    }
    for (int i = 2; i < Maxn; ++i)
        Mu[i] += Mu[i - 1];
}

inline LL Solve ()
{
    N /= D;
    M /= D;
    int last;
    if (N > M) swap(N, M);
    LL Ans = 0ll;
    for (int i = 1; i <= N; i = last + 1)
    {
        last = min(N / (N / i), M / (M / i));
        Ans += 1LL * (Mu[last] - Mu[i - 1]) * (N / i) * (M / i);
    }
    return Ans;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    Init();
    while (T--)
    {
        scanf("%d%d%d", &N, &M, &D);
        printf("%lld\n", Solve());
    }
    return 0;
}