莫比乌斯反演（acwing2702）

对于给出的?n�?个询问，每次求有多少个数对?(x,y)(�,�)，满足?a≤x≤b，c≤y≤d�≤�≤�，�≤�≤�，且?gcd(x,y)=kgcd(�,�)=�，gcd(x,y)gcd(�,�)?函数为?x�?和?y�?的最大公约数。

输入格式

第一行一个整数?n�。

接下来?n�?行每行五个整数，分别表示?a、b、c、d、k�、�、�、�、�。

输出格式

共?n�?行，每行一个整数表示满足要求的数对?(x,y)(�,�)?的个数。

数据范围

1≤n≤500001≤�≤50000,
1≤a≤b≤500001≤�≤�≤50000,
1≤c≤d≤500001≤�≤�≤50000,
1≤k≤500001≤�≤50000

输入样例：

2
2 5 1 5 1
1 5 1 5 2

输出样例：

14
3

思路：

可以设f(k,x,y)为对于1<=i<=x,1<=j<=y,有多少组合gcd(i,j)=k

根据莫比乌斯反演可以设F（k,x,y）为?1<=i<=x,1<=j<=y，有多少组合满足k|gcd(i,j)

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double eps = 1e-8;
const int N = 50000+1000;
#define LL long long?
int pre[N], mu[N],st[N];
int n,a,b,c,d,k,cn;
long long res;
void into()
{
? ? mu[1] = 1;
? ? for (int i = 2; i <= N; i++)
? ? {
? ? ? ? if (!st[i]) pre[++cn] = i, mu[i] = -1;
? ? ? ? for (int j = 1; pre[j] * i <= N&&j<=cn; j++)
? ? ? ? {
? ? ? ? ? ? st[pre[j] * i] = 1;
? ? ? ? ? ? if (i % pre[j] == 0) break;
? ? ? ? ? ? mu[i*pre[j]] = -mu[i];
? ? ? ? }
? ? }
? ? for (int i = 1; i <= N; i++)
? ? ? ? mu[i] += mu[i - 1];
}
int g(int l, int k)
{
? ? if (k / l==0) return n;
? ? return k /(k / l);
}
long long f(int a, int b)
{
? ? res = 0;
? ? n = min(a, b);
? ? int x = a / k, y = b / k;
? ? for (int i = 1,j=1; i <=n; i=j+1)
? ? { ??
? ? ? ? ?j = min(n, min(g(i,x),g(i,y)));
? ? ? ? res += (LL)(mu[j] - mu[i - 1])*(x/i)*(y/i);
? ? }
? ? return res;
}
int main()
{
? ? into();
? ? int T;
? ? cin >> T;
? ? while (T--)
? ? {
? ? ? ? cin >> a >> b >> c >> d >> k;
? ? ? ? cout << f(b, d) - f(a-1, d) - f(b, c-1) + f(a-1, c-1) << endl;
? ? }
? ? return 0;
}?