合理运用数论函数——CF1295D Same GCDs

Sweetlemon

2020-01-31 00:18:58

Solution

### [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; } ```