合理运用数论函数——CF1295D Same GCDs
Sweetlemon
2020-01-31 00:18:58
### [CF1295D Same GCDs](https://www.luogu.com.cn/problem/CF1295D)
#### 题意
给定两个整数 $a,m\ (1\le a<m\le 10^{10})$。计算满足条件 $0 \le x < m$ 且 $\gcd(a,m)=\gcd(a+x,m)$ 的整数 $x$ 的个数。
#### 简单转化
首先可以注意到,$a$ 和 $m$ 都是已知的,因此可以求出 $a,m$ 的最大公因数 $g$。那么,$\gcd(a,m)=\gcd(a+x,m)=g\ (0\le x<m)$ 就等价于 $\gcd(a',m')=\gcd(a'+x',m')=1\ (0\le x'<m')$,其中 $a',m',x'$ 满足 $a=ga',\ m=gm',x=gx'$。
下文中将整数 $u$ 与 $v$ 互质记作 $u\perp v$。为下文叙述方便起见,转化完成后,我们令 $a=a',m=m',x=x'$,即假设我们已经把 $a$ 和 $m$ 都除以了 $g$。那么我们现在就是已知 $a\perp m$,想求满足 $(a+x)\perp m,0\le x<m$ 的整数 $x$ 的个数。
#### 方法 1:莫比乌斯函数
看到“互质”,通常就可以用莫比乌斯函数进行转化了。
$$\begin{aligned}&\sum^{m-1}_{x=0}[(a+x)\perp m]\\=&\sum^{m-1}_{x=0}\sum_{d\mid (a+x)\ \land\ d\mid m}\mu(d)\\=&\sum_{d\mid m}\mu(d)\sum^{m-1}_{x=0}[d\mid (a+x)]\\=&\sum_{d\mid m}\mu(d)\left (\left \lfloor \frac{a+m-1}{d} \right\rfloor-\left\lfloor \frac{a-1}{d} \right\rfloor\right )\end{aligned}$$
第一行是原始统计量,第二行用了 $\sum_{d\mid x}\mu(d)=[x=1]$ 的常见转化,第三行交换了 $x,d$ 两层求和的顺序,第四行把内层求和用式子简化了。
于是现在我们只需对 $m$ 的每一个约数进行上述求和即可。那么我们需要找出 $m$ 的每一个约数,还要算出它每一个约数的 $\mu$ 值。
找约数自然可以 $\mathrm{O}(\sqrt{m})$ 找,那 $\mu$ 值怎么算呢?
设 $m$ 有 $t$ 个不同的质因子,那么实际上 $m$ 只有 $2^t$ 个约数的 $\mu$ 非零,而通过计算发现 $m\le 10^{10}$ 时 $t\le 10$,因此我们只需把 $m$ 质因数分解,再枚举 $m$ 质因子集合的子集,计算出相应的无平方因子约数,更新答案即可。
总时间复杂度 $\mathrm{O}(\sqrt{m}+2^t)=\mathrm{O}(\sqrt{m})$。
#### 方法 2:欧拉函数
赛时我也一度猜想答案就是 $\varphi(m)$,但是因为一时无法证明,并且方法 1 也能想出来,因此就没有更深入地探究。赛后看到讨论区有这个方法,就仔细想了想,还是比较妙的。
既然我们想要证明答案是 $\varphi(m)$,那么我们就要把 “所有与 $m$ 互质的(下文称为合法的)$a+x$” 和 “$[1,m]$ 中所有与 $m$ 互质的整数” 一一对应起来。下面构造一个这样的一一对应。
1. 若 $0\le x\le m-a$,则 $a\le a+x\le m$,合法的 $a+x$ 一一对应 $[a,m]$ 中与 $m$ 互质的数。
2. 若 $m-a+1\le x< m$,则 $m+1\le a+x\le m+a-1$。因为 $\gcd(u+v,v)=\gcd(u,v)$,所以 $u\perp v \Leftrightarrow (u+v)\perp v$,于是我们得到 $(a+x)\perp m\Leftrightarrow (a+x-m)\perp m$。因此合法的 $a+x$ 一一对应 $[1,a-1]$ 中与 $m$ 互质的数。
综上,所有与 $m$ 互质的 $a+x$ 一一对应 $[1,m]$ 中所有与 $m$ 互质的整数,有 $\varphi(m)$ 个。于是我们只需要求出 $\varphi(m)$ 作为答案即可。
这种方法只需要求 $\varphi(m)$,需要对 $m$ 进行质因数分解,时间复杂度 $\mathrm{O}(\sqrt{m})$。
#### 拓展
事实上,任意 $m$ 个连续正整数中与 $m$ 互质的数的个数恰为 $\varphi(m)$;或者说,把这道题中 $a<m$ 的条件去除,答案不变。这个结论可以用上述两种方法来证明。
**用 $\mu$ 证明。** 设 $a=qm+r\ (q,r\in \mathbb{N},0\le r<m)$,则答案式可以进行如下化简:
$$\begin{aligned}&\sum_{d\mid m}\mu(d)\left (\left \lfloor \frac{a+m-1}{d} \right\rfloor-\left\lfloor \frac{a-1}{d} \right\rfloor\right )\\=&\sum_{d\mid m}\mu(d)\left (\left \lfloor \frac{qm+r+m-1}{d} \right\rfloor-\left\lfloor \frac{qm+r-1}{d} \right\rfloor\right )\\=&\sum_{d\mid m}\mu(d)\left (\frac{qm}{d}+\left \lfloor\frac{r+m-1}{d} \right\rfloor-\frac{qm}{d}-\left\lfloor \frac{r-1}{d} \right\rfloor\right )\\=&\sum_{d\mid m}\mu(d)\left (\left \lfloor\frac{r+m-1}{d} \right\rfloor-\left\lfloor \frac{r-1}{d} \right\rfloor\right )\\=&\varphi(m)\end{aligned}$$
第一行带入了方法一的答案式子,第二行把 $a$ 代换为 $qm+r$,第三行利用了整数可以自由移出取整符号的性质,第四行把 $\frac{qm}{d}$ 去除,第五行运用了题目中答案的性质。
**用映射方法证明。** 取这连续 $m$ 个正整数模 $m$ 的余数,一定分别是 $0,1,\cdots,m-1$。我们把这些正整数根据模 $m$ 的余数从小到大排序,分别记为 $n_0,n_1,\cdots,n_k,\cdots,n_{m-1}$;也就是说,$n_k\equiv k\pmod{m}$。由于 $\gcd(a,b)=\gcd(b,a\%b)$,因此 $\gcd(n_k,m)=\gcd(m,k)$,于是我们得到 $n_k\perp m\Leftrightarrow k\perp m$,这样我们就建立了“$n_0,\cdots,n_{m-1}$ 当中与 $m$ 互质的整数”和“$[0,m-1]$ 中与 $m$ 互质的整数”的一一对应(假设 $0$ 不与任何数互质;$m=1$ 的情况特殊,可以单独拿出来讨论)。因此,任意连续 $m$ 个正整数当中,与 $m$ 互质的数一共有 $\varphi(m)$ 个。
同时通过这道题的推导,我们也得到了 $\varphi$ 函数用约数的 $\mu$ 函数表达的式子 $\varphi(n)=\sum_{d\mid n} \mu(d)\frac{n}{d}$,也就是 $\varphi=\mu*\mathrm{id}$。
#### 代码
提供 $\mu$ 版本和 $\varphi$ 版本的代码。
$\mu$ 版本:
```cpp
//Submitted on luogu, mu version
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>
#define MAXIOLG 25
using namespace std;
//Constant area
#define MAXN 109005
typedef long long ll;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快读,实现略去
void ayano(io_t x,char spliter='\n'); //快写,实现略去
ll prs[MAXN]; //存储质因子
ll gcd(ll a,ll b);
int main(void){
int testcases=seto();
while (testcases--){
ll a,m,g;
ll ans=0;
a=seto(),m=seto(),g=gcd(a,m),a/=g,m/=g;
if (m==1){
ayano(1);
continue;
}
ll sqrm=sqrt(m)+2;
ll mm=m;
int prcnt=0;
for (int i=2;i<=sqrm;i++){
if (m/i*i!=m)
continue;
prcnt++,prs[prcnt]=i;
while (m/i*i==m)
m/=i;
}
if (m>1)
prcnt++,prs[prcnt]=m;
m=mm;
//枚举无平方因子的约数
int ful=1<<prcnt;
for (int i=0;i<ful;i++){
ll res=1;
int tmu=1;
int j=i;
for (int k=1;k<=prcnt;k++){
if (j&1)
res*=prs[k],tmu=-tmu;
j>>=1;
}
ans+=1ll*tmu*((a+m-1)/res-(a-1)/res);
}
ayano(ans);
}
return 0;
}
ll gcd(ll a,ll b){
ll t;
while (b)
t=a,a=b,b=t%b;
return a;
}
```
$\varphi$ 版本:
```cpp
//Submitted on luogu, phi version
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>
#define MAXIOLG 25
using namespace std;
//Constant area
#define MAXN 109005
typedef long long ll;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快读,实现略去
void ayano(io_t x,char spliter='\n'); //快写,实现略去
ll gcd(ll a,ll b);
int main(void){
int testcases=seto();
while (testcases--){
ll a,m,g;
a=seto(),m=seto(),g=gcd(a,m),a/=g,m/=g;
ll sqrm=sqrt(m)+2;
ll ans=m;
for (int i=2;i<=sqrm;i++){
if (m/i*i!=m)
continue;
ans/=i,ans*=(i-1);
while (m/i*i==m)
m/=i;
}
if (m>1)
ans/=m,ans*=(m-1);
ayano(ans);
}
return 0;
}
ll gcd(ll a,ll b){
ll t;
while (b)
t=a,a=b,b=t%b;
return a;
}
```