『Zap Möbius反演』

<更新提示>

<第一次更新>


<正文>

Zap

Description

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

Input Format

第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个 正整数,分别为a,b,d。(1<=d<=a,b<=50000)

Output Format

对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。

Sample Input

2
4 5 2
6 4 3

Sample Output

3
2

解析

按照题意,可以直接设一个数论函数$$f(d)=\sum_{x=1}a\sum_{y=1}b[gcd(x,y)=d]$$

代表\([1,a],[1,b]\)范围内最大公因数为\(d\)的二元组个数。

可是这个函数好像比较难求,考虑\(Möbius\)反演。我们发现有函数

\[F(n)=\sum_{n|d}f(d)
\]

比较好求。即\(F(n)\)代表\([1,a],[1,b]\)范围内最大公约数为\(n\)倍数的二元组个数,只需满足二元组\((x,y)\)都是\(n\)倍数即可,所以有

\[F(n)=\lfloor \frac{a}{n} \rfloor\lfloor \frac{b}{n} \rfloor
\]

然后套\(Möbius\)定理,得到

\[f(d)=\sum_{d|n}\mu(\frac{n}{d})F(n)
\]

对于求解\(f(d)\),有

\[f(d)=\sum_{d|n}\mu(\frac{n}{d})F(n)=\sum_{d|n}\mu(\frac{n}{d})\lfloor \frac{a}{n} \rfloor\lfloor \frac{b}{n} \rfloor
\]

设\(t=\frac{n}{d}\),由于\(\lfloor \frac{a}{n} \rfloor\lfloor \frac{b}{n} \rfloor\)在\(n\leq\min(a,b)\)时有值,所以\(1\leq t\leq\frac{\min(a,b)}{d}\),则

\[f(d)=\sum_{t=1}^{\frac{\min(a,b)}{d}}\mu(t)\lfloor \frac{a}{td} \rfloor\lfloor \frac{b}{td} \rfloor
\]

然后就可以求\(f(d)\)的值了,由于系数\(\lfloor \frac{a}{td} \rfloor\lfloor \frac{b}{td} \rfloor\)是下取整形式的,就可以整除分块一下,对每一块相同的部分一起计算一下即可。

\(Code:\)

#include <bits/stdc++.h>
using namespace std;
const int N=60020,Uplim=5e4;
int a,b,k,vis[N],Prime[N],mui[N],cnt,sum[N],ans;
inline void input(void)
{
scanf("%d%d%d",&a,&b,&k);
}
inline void sieve(void)
{
mui[1] = 1;
for (int i=2;i<=Uplim;i++)
{
if (!vis[i])Prime[++cnt] = i , mui[i] = -1;
for (int j=1;j<=cnt&&i*Prime[j]<=Uplim;j++)
{
vis[ i*Prime[j] ] = true;
if (i%Prime[j]==0)break;
mui[ i*Prime[j] ] = -mui[i];
}
}
}
inline void init(void)
{
for (int i=1;i<=Uplim;i++)
sum[i] = sum[i-1] + mui[i];
}
inline void solve(void)
{
ans = 0 , a /= k , b /= k;
for (int l=1,r;l<=min(a,b);l=r+1)
{
r = min( a/(a/l) , b/(b/l) );
ans += (a/l) * (b/l) * (sum[r]-sum[l-1]);
}
}
int main(void)
{
sieve();
init();
int T;
scanf("%d",&T);
while (T--)
{
input();
solve();
printf("%d\n",ans);
}
return 0;
}

<后记>

上一篇:Linux指令装图像化界面


下一篇:angular,vue,react的基本语法—动态属性、事件绑定、ref,angular组件创建方式