[POI2007]ZAP-Queries

标签： 数学 莫比乌斯反演

---

题目描述

FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足1<=x<=a，1<=y<=b，并且gcd（x, y）=d。作为FGD的同学，FGD希望得到你的帮助。

输入输出格式

输入格式：
The first line of the standard input contains one integer nnn (1≤n≤50 000),denoting the number of queries.

The following nnn lines contain three integers each: aaa, bbb and ddd(1≤d≤a,b≤50 000), separated by single spaces.

Each triplet denotes a single query.

输出格式：
Your programme should write nnn lines to the standard output. The i’th line should contain a single integer: theanswer to the iii’th query from the standard input.

输入输出样例

输入样例#1：
2
4 5 2
6 4 3
输出样例#1：
3
2

题解

最近在学习莫比（懵逼）乌斯反演，这道题应该算是入门题了吧。
根据dalao们说按照套路我们设:
$$f(x)=\sum_{i = 1}^{a}\sum_{j = 1}^{b}[gcd(i, j) = x]$$
$$F(x)=\sum_{x|n}f(n)=\left \lfloor \frac{a}{n} \right \rfloor\left \lfloor \frac{b}{n} \right \rfloor$$
通俗点说，即我们设$f(x):gcd(i, j) = x的对数$.
设$F(x):gcd(i, j) = x 和 x倍数的对数$
然后就是化简式子:
$Ans = f(x)$
$Ans = \sum_{x|n}u(\frac{n}{x})F(n)$（莫比乌斯反演）
更改枚举项为$\frac{n}{x}$
$$Ans = \sum_{p = 1}^{min(\left \lfloor \frac{a}{x} \right \rfloor, \left \lfloor \frac{b}{x} \right \rfloor)} u(p)F(xp)$$
化简到这里，我们就可以在O(n)的时间做出这道题了,如果有多组数据那么我们需要用整除分块（这个可以百度）

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define N 60010
#define ll long long
using namespace std;

int n, a, b, d, cnt = 0;
int pri[N], u[N], sum[N];
bool vis[N];

void get()
{
    int t = N - 10; u[1] = 1;
    for(int i = 2; i <= t; i ++)
    {
        if(!vis[i]) pri[++ cnt] = i, u[i] = -1;
        for(int j = 1; j <= cnt && pri[j] * i <= t; j ++)
        {
            vis[i * pri[j]] = true;
            if(i % pri[j] == 0) break;
            else u[i * pri[j]] = -u[i];
        }
    }
    for(int i = 1; i <= t; i ++) sum[i] = sum[i - 1] + u[i];
}

int main()
{
    get();
    scanf("%d", &n);
    while(n --)
    {
        ll ans = 0;
        scanf("%d%d%d", &a, &b, &d);
        int t = min(a / d, b / d);
        for(int l = 1, r; l <= t; l = r + 1)
        {
            r = min((a / d) / ((a / d) / l), (b / d) / ((b / d) / l));
            ans += 1ll * (sum[r] - sum[l - 1]) * (a / (d * l)) * (b / (d * l));    
        }
        printf("%lld\n", ans);
    }
    return 0;
} 

心得

感觉莫比乌斯反演的题目特别考察式子的化简，特别是更改枚举项之类的，还是要做多题来积累化简式子的能力