$1 \leq x \leq a {~}1 \leq y \leq b$
$gcd(x,y)=d$
<=>
$1 \leq x’ \leq {\frac{a}{d}}^{向下取整}=a’ {~~~} 1 \leq y’ \leq \frac{b}{d}^{向下取整}=b’$
$gcd(x’,y’)=1$
<=>
每次询问相当于问有多少对$x’$和$y’$是互质的
<=>
互斥原理(总对数-不互质数=(单因子对数+双因子-三因子+四因子-…))
$$a’b’-{\frac{a’}{2}}^{向下取整}{\frac{b’}{2}}^{向下取整}-{\frac{a’}{3}}^{向下取整}{\frac{b’}{3}}^{向下取整}-…\\\\
+{\frac{a’}{6}}^{向下取整}{\frac{b’}{6}}^{向下取整}+…\\\\
-{\frac{a’}{30}}^{向下取整}{\frac{b’}{30}}^{向下取整}-…\\\\
+…\\\\
=a’b’+\sum_{i=1}^{min(a’,b’)}{\frac{a’}{i}}^{向下取整}{\frac{b’}{i}}^{向下取整} \times mobius[i]
$$
$$ mobius(i)= \begin{cases} 0, i=p_{k}^{2+} \\\\ (-1)^{i}, i = p_{1}…p_{k} \\\\ 1, i=1 \end{cases} $$
$
\frac{a}{1} {~} \frac{a}{2} ....{~} \frac{a}{a}中 最多2\sqrt{a}个不同的数\\\\
a个数可以分为2\sqrt{a}段 ,每段数都是相同的\\\\
{\frac{a’}{i}}^{向下取整}{\frac{b’}{i}}^{向下取整}部分可以用先处理好前缀和做O(\sqrt{n})
$
如何分区间?
$$
{\frac{a’}{x}}^{向下取整} = {\frac{a’}{g(x)}}^{向下取整} 且 {\frac{a’}{x}}^{向下取整}>{\frac{a’}{g(x)+1}}^{向下取整}
$$
$$
{\frac{24}{9}}^{向下取整} {~} {\frac{24}{10}}^{向下取整} {~} {\frac{24}{11}}^{向下取整} {~} {\frac{24}{12}}^{向下取整} \\\\
g(9)=12\\\\
g(x) = {\frac{a}{{a/x}^{向下取整}}}^{向下取整}
$$
${\frac{a}{x}}^{向下取整}=={\frac{a}{g(x)}}^{向下取整}$的证明
对于第二个等式,左边分母去掉向下取整之后,分母变大,整个函数变小(而此时$=={\frac{a}{x}}^{向下取整}==$右边),所以变小之前$≥$右边
${\frac{a’}{x}}^{向下取整}>{\frac{a’}{g(x)+1}}^{向下取整}$的证明
两次构造余数表达式
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 50010;
int primes[N], cnt;
bool st[N];
int mobius[N], sum[N];
// 线性筛法,求莫比乌斯函数
void init(int n)
{
mobius[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
mobius[i] = -1;//质数乘积表达式中只有一个质数
}
for (int j = 0; primes[j] * i <= n; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
// 此时t=primes[j]*primes[j]*i/primes[j] 包含多个primes[j]
mobius[t] = 0;
break;
}
// p[j]只有一个 则t中是否包含多个重复质因子取决于i中是否包含多个重复质因子
mobius[t] = mobius[i] * -1;
}
}
for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + mobius[i];
}
int main()
{
init(N-1);
int T;
cin >> T;
while(T--)
{
int a,b,d;
cin >> a >> b >> d;
a/=d,b/=d;//a',b'
int n = min(a,b);
LL res= 0;
// 相同数区间长度*区间中mobius系数和
// l,r表示每一段左右边界
// 取min(a / (a / l), b / (b / l)))是因为取更大的话 小的那个数/pipj就=0了
for (int l = 1, r; l <= n; l = r + 1)
{
r = min(n, min(a / (a / l), b / (b / l)));
res += (sum[r] - sum[l - 1]) * (LL)(a / l) * (b / l);
}
printf("%lld\n", res);
}
return 0;
}
想问一下你这里没有a’/4*b’/4的情况,那么为什么L是从1枚举到min(a,b),不连续,是因为mo bius函数如果某个因子含有个数>1所以为0,所以才能连续的,这么理解正确吗
时间过太久了,已经忘了orz