莫比乌斯反演 – Mophues – HDU 4746
题意：
计
算
满
足
g
c
d
(
a
,
b
)
=
k
，
其
中
1
≤
a
≤
n
，
1
≤
b
≤
m
且
k
的
质
因
子
(
可
重
复
)
数
≤
P
计算满足gcd(a,b)=k，其中1\le a \le n，1\le b\le m 且k的质因子(可重复)数\le P
计
算
满
足
g
c
d
(
a
,
b
)
=
k
，
其
中
1
≤
a
≤
n
，
1
≤
b
≤
m
且
k
的
质
因
子
(
可
重
复
)
数
≤
P
的
数
对
(
a
,
b
)
的
个
数
。
的数对(a,b)的个数。
的
数
对
(
a
,
b
)
的
个
数
。
Input
The first line of input is an integer Q meaning that there are Q test cases.
Then Q lines follow, each line is a test case and each test case contains three non-negative numbers: n, m and P (n, m, P <= 5×10
5
. Q <=5000).
Output
For each test case, print the number of pairs (a, b), which 1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of P.
Sample Input
2
10 10 0
10 10 1
Sample Output
63
93
分析：
设
f
(
x
)
为
x
的
所
有
质
因
子
(
可
重
复
)
的
个
数
。
设f(x)为x的所有质因子(可重复)的个数。
设
f
(
x
)
为
x
的
所
有
质
因
子
(
可
重
复
)
的
个
数
。
由
题
意
，
即
计
算
：
由题意，即计算：
由
题
意
，
即
计
算
：
∑
a
=
1
n
∑
b
=
1
m
[
f
(
g
c
d
(
a
,
b
)
)
≤
p
]
\sum_{a=1}^n\sum_{b=1}^m[f(gcd(a,b))\le p]
a
=
1
∑
n
b
=
1
∑
m
[
f
(
g
c
d
(
a
,
b
)
)
≤
p
]
把
g
c
d
的
结
果
提
取
出
来
计
数
：
把gcd的结果提取出来计数：
把
g
c
d
的
结
果
提
取
出
来
计
数
：
∑
a
=
1
n
∑
b
=
1
m
[
f
(
g
c
d
(
a
,
b
)
)
≤
p
]
=
∑
d
=
1
m
i
n
(
n
,
m
)
[
f
(
d
)
≤
p
]
∑
a
=
1
n
∑
b
=
1
m
[
g
c
d
(
a
,
b
)
=
=
d
]
\sum_{a=1}^n\sum_{b=1}^m[f(gcd(a,b))\le p]=\sum_{d=1}^{min(n,m)}[f(d)\le p]\sum_{a=1}^n\sum_{b=1}^m[gcd(a,b)==d]
a
=
1
∑
n
b
=
1
∑
m
[
f
(
g
c
d
(
a
,
b
)
)
≤
p
]
=
d
=
1
∑
m
i
n
(
n
,
m
)
[
f
(
d
)
≤
p
]
a
=
1
∑
n
b
=
1
∑
m
[
g
c
d
(
a
,
b
)
=
=
d
]
根
据
反
演
定
理
，
很
容
易
求
出
：
根据反演定理，很容易求出：
根
据
反
演
定
理
，
很
容
易
求
出
：
∑
a
=
1
n
∑
b
=
1
m
[
g
c
d
(
a
,
b
)
=
=
d
]
=
∑
d
∣
x
m
i
n
(
n
,
m
)
μ
(
x
d
)
⌊
n
x
⌋
⌊
m
x
⌋
=
∑
i
=
1
m
i
n
(
n
d
,
m
d
)
μ
(
i
)
⌊
n
d
i
⌋
⌊
m
d
i
⌋
\sum_{a=1}^n\sum_{b=1}^m[gcd(a,b)==d]=\sum_{d|x}^{min(n,m)}\mu(\frac{x}{d})\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor=\sum_{i=1}^{min(\frac{n}{d},\frac{m}{d})}\mu(i)\lfloor\frac{\frac{n}{d}}{i}\rfloor\lfloor\frac{\frac{m}{d}}{i}\rfloor
a
=
1
∑
n
b
=
1
∑
m
[
g
c
d
(
a
,
b
)
=
=
d
]
=
d
∣
x
∑
m
i
n
(
n
,
m
)
μ
(
d
x
)
⌊
x
n
⌋
⌊
x
m
⌋
=
i
=
1
∑
m
i
n
(
d
n
,
d
m
)
μ
(
i
)
⌊
i
d
n
⌋
⌊
i
d
m
⌋
从
而
：
从而：
从
而
：
∑
a
=
1
n
∑
b
=
1
m
[
f
(
g
c
d
(
a
,
b
)
)
≤
p
]
=
∑
d
=
1
m
i
n
(
n
,
m
)
[
f
(
d
)
≤
p
]
∑
d
∣
x
m
i
n
(
n
,
m
)
μ
(
x
d
)
⌊
n
x
⌋
⌊
m
x
⌋
\sum_{a=1}^n\sum_{b=1}^m[f(gcd(a,b))\le p]=\sum_{d=1}^{min(n,m)}[f(d)\le p]\sum_{d|x}^{min(n,m)}\mu(\frac{x}{d})\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor
a
=
1
∑
n
b
=
1
∑
m
[
f
(
g
c
d
(
a
,
b
)
)
≤
p
]
=
d
=
1
∑
m
i
n
(
n
,
m
)
[
f
(
d
)
≤
p
]
d
∣
x
∑
m
i
n
(
n
,
m
)
μ
(
d
x
)
⌊
x
n
⌋
⌊
x
m
⌋
上
式
我
们
是
先
枚
举
了
d
，
再
枚
举
其
倍
数
x
，
进
行
求
和
，
上式我们是先枚举了d，再枚举其倍数x，进行求和，
上
式
我
们
是
先
枚
举
了
d
，
再
枚
举
其
倍
数
x
，
进
行
求
和
，
我
们
发
现
，
∑
⌊
n
x
⌋
⌊
m
x
⌋
这
一
块
可
以
通
过
整
除
分
块
做
到
O
(
n
)
，
我们发现，\sum\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor这一块可以通过整除分块做到O(\sqrt{n})，
我
们
发
现
，
∑
⌊
x
n
⌋
⌊
x
m
⌋
这
一
块
可
以
通
过
整
除
分
块
做
到
O
(
n
)
，
我
们
的
目
标
就
是
能
够
快
速
预
处
理
出
∑
f
(
d
)
μ
(
x
d
)
的
前
缀
和
，
我们的目标就是能够快速预处理出\sum f(d)\mu(\frac{x}{d})的前缀和，
我
们
的
目
标
就
是
能
够
快
速
预
处
理
出
∑
f
(
d
)
μ
(
d
x
)
的
前
缀
和
，
所
以
，
我
们
交
换
求
和
次
序
，
先
枚
举
其
倍
数
x
，
再
枚
举
x
的
约
数
d
，
上
式
等
价
于
：
所以，我们交换求和次序，先枚举其倍数x，再枚举x的约数d，上式等价于：
所
以
，
我
们
交
换
求
和
次
序
，
先
枚
举
其
倍
数
x
，
再
枚
举
x
的
约
数
d
，
上
式
等
价
于
：
∑
a
=
1
n
∑
b
=
1
m
[
f
(
g
c
d
(
a
,
b
)
)
≤
p
]
=
∑
x
=
1
m
i
n
(
n
,
m
)
⌊
n
x
⌋
⌊
m
x
⌋
∑
d
∣
x
m
i
n
(
n
,
m
)
μ
(
x
d
)
[
f
(
d
)
≤
p
]
\sum_{a=1}^n\sum_{b=1}^m[f(gcd(a,b))\le p]=\sum_{x=1}^{min(n,m)} \lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor \sum_{d|x}^{min(n,m)}\mu(\frac{x}{d}) [f(d)\le p]
a
=
1
∑
n
b
=
1
∑
m
[
f
(
g
c
d
(
a
,
b
)
)
≤
p
]
=
x
=
1
∑
m
i
n
(
n
,
m
)
⌊
x
n
⌋
⌊
x
m
⌋
d
∣
x
∑
m
i
n
(
n
,
m
)
μ
(
d
x
)
[
f
(
d
)
≤
p
]
接
着
，
我
们
考
虑
如
何
预
处
理
后
一
半
的
前
缀
和
。
接着，我们考虑如何预处理后一半的前缀和。
接
着
，
我
们
考
虑
如
何
预
处
理
后
一
半
的
前
缀
和
。
观
察
到
数
据
范
围
在
5
×
1
0
5
以
内
，
可
知
f
(
x
)
的
结
果
不
超
过
19
，
所
以
我
们
仅
需
对
p
≤
19
的
情
况
做
预
处
理
。
观察到数据范围在5×10^5以内，可知f(x)的结果不超过19，所以我们仅需对p\le 19的情况做预处理。
观
察
到
数
据
范
围
在
5
×
1
0
5
以
内
，
可
知
f
(
x
)
的
结
果
不
超
过
1
9
，
所
以
我
们
仅
需
对
p
≤
1
9
的
情
况
做
预
处
理
。
①
、
当
p
≤
19
时
，
对
每
一
个
p
，
我
们
预
处
理
出
g
[
x
]
[
p
]
=
∑
d
∣
x
m
i
n
(
n
,
m
)
μ
(
x
d
)
[
f
(
d
)
≤
p
]
，
并
计
算
其
前
缀
和
数
组
s
u
m
[
x
]
[
p
]
=
∑
x
=
1
m
i
n
(
n
,
m
)
∑
d
∣
x
m
i
n
(
n
,
m
)
μ
(
x
d
)
[
f
(
d
)
≤
p
]
。
①、当p\le 19时，对每一个p，我们预处理出g[x][p]=\sum_{d|x}^{min(n,m)}\mu(\frac{x}{d}) [f(d)\le p]，\\\ \\ \qquad并计算其前缀和数组sum[x][p]=\sum_{x=1}^{min(n,m)} \sum_{d|x}^{min(n,m)}\mu(\frac{x}{d}) [f(d)\le p]。
①
、
当
p
≤
1
9
时
，
对
每
一
个
p
，
我
们
预
处
理
出
g
[
x
]
[
p
]
=
∑
d
∣
x
m
i
n
(
n
,
m
)
μ
(
d
x
)
[
f
(
d
)
≤
p
]
，
并
计
算
其
前
缀
和
数
组
s
u
m
[
x
]
[
p
]
=
∑
x
=
1
m
i
n
(
n
,
m
)
∑
d
∣
x
m
i
n
(
n
,
m
)
μ
(
d
x
)
[
f
(
d
)
≤
p
]
。
这
里
，
我
们
又
将
其
分
为
两
小
步
：
\qquad 这里，我们又将其分为两小步：
这
里
，
我
们
又
将
其
分
为
两
小
步
：
首
先
，
要
预
处
理
出
g
[
x
]
[
f
(
d
)
]
=
∑
d
∣
x
m
i
n
(
n
,
m
)
μ
(
x
d
)
，
再
对
g
数
组
从
1
到
19
求
前
缀
和
。
\qquad 首先，要预处理出g[x][f(d)]=\sum_{d|x}^{min(n,m)}\mu(\frac{x}{d})，再对g数组从1到19求前缀和。
首
先
，
要
预
处
理
出
g
[
x
]
[
f
(
d
)
]
=
∑
d
∣
x
m
i
n
(
n
,
m
)
μ
(
d
x
)
，
再
对
g
数
组
从
1
到
1
9
求
前
缀
和
。
然
后
，
求
前
缀
和
数
组
s
u
m
[
i
]
[
p
]
=
s
u
m
[
i
−
1
]
[
p
]
+
g
[
i
]
[
p
]
\qquad 然后，求前缀和数组sum[i][p]=sum[i-1][p]+g[i][p]
然
后
，
求
前
缀
和
数
组
s
u
m
[
i
]
[
p
]
=
s
u
m
[
i
−
1
]
[
p
]
+
g
[
i
]
[
p
]
②
、
当
p
>
19
时
，
所
有
数
对
均
符
合
条
件
，
答
案
为
n
×
m
。
②、当p>19时，所有数对均符合条件，答案为n×m。
②
、
当
p
>
1
9
时
，
所
有
数
对
均
符
合
条
件
，
答
案
为
n
×
m
。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<queue>
#define ll long long
using namespace std;
const int N = 5e5 + 10;
int T, n, m, P;
int primes[N], mu[N], cnt;
int f[N]; //f[i]: i的质因子个数
bool st[N];
ll g[N][30];
ll sum[N][30];
void get_prime(int n)
{
f[1]=0;
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
mu[i]=-1;
f[i]=1;
}
for(int j=0;primes[j]*i<=n;j++)
{
int p = primes[j];
st[p*i]=true;
f[i*p]=f[i]+1;
if(i%p==0)
{
mu[i*p]=0;
break;
}
mu[i*p]=-mu[i];
}
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
g[j][f[i]] += mu[j/i];
for(int i=1;i<=n;i++)
for(int p=1;p<=19;p++)
g[i][p] += g[i][p-1];
for(int i=1;i<=n;i++)
for(int p=0;p<=19;p++)
sum[i][p] = sum[i-1][p]+g[i][p];
}
ll cal(int n,int m,int p)
{
ll res = 0;
for(int l=1, r=1;l<=min(n,m);l=r+1)
{
r=min(n/(n/l),m/(m/l));
r=min(r,min(n,m));
res += (ll)(sum[r][p]-sum[l-1][p])*(n/l)*(m/l);
}
return res;
}
int main()
{
get_prime(N-1);
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&P);
if(P>19) printf("%lld\n",(ll)n*m);
else printf("%lld\n",cal(n,m,P));
}
return 0;
}