数论 GCD 最大公约数 欧拉函数经典题 洛谷 CF1295D Same GCDs Codeforces1295D

​前言

两个月了，我终于更了……

这两个月忙（chen）于（mi）内（xiang）卷（le），现在终于出新文章啦，（也算兑现了当初的出数论题文章的承诺）~

不说废话了，今天给大家介绍一道CF/洛谷上的数论题———CF1295D Same GCDs/1295D #81 Problem D。

这是一道相当不错的题，很考验选手的思维能力以及数学基础，先贴个题面~

洛谷题目传送门 or Codeforces题目传送门​​​​​​​​​​​​​​​​​​

题目描述

You are given two integers $a$ and $m$ . Calculate the number of integers $x$ such that $0\le x<m$ and $gcd(a,m)$ = $gcd(a+x,m)$.

Note: gcd(a, b) is the greatest common divisor of $a$ and $b$ .

输入格式

The first line contains the single integer $T$($1\le T\le 50$) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains two integers $a$ and $m$ ($1\le a<m\le 10^{10}$) .

输出格式

Print $T$ integers — one per test case. For each test case print the number of appropriate $x$ -s.

题意翻译

求 $$\sum _{i=1}^n[gcd(a,m)=gcd(a+x,m)]$$

多组测试数据, $T\le 50,1\le a<m\le 10$

输入输出样例

输入 #1

3
4 9
5 10
42 9999999967

输出 #1

6
1
9999999966

​说明/提示

In the first test case appropriate $x$ -s are [$0,1,3,4,6,7$].

In the second test case the only appropriate $x$ is $0$ .

解题思路

那么，看完题目，第一反应肯定是这题正解绝对不是用暴力，真要暴力的话你会在某Online Judge得到优秀的40pts
所以，我们要费点功夫，处理一下这个式子。

前置芝士 ———欧拉函数

是的，这题也绕不开欧拉，那么，什么是欧拉函数呢？
定义：在数论中，对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目。
贴张书照———

（出自长乐一中董永建老师团队所撰书籍《信息学奥赛一本通高效进阶》，侵删。）
那么，简单来讲，欧拉函数$\phi (n)$就表示小于$n$又与$n$互质的数的数量。
几个基本性质：

1. 设$n$=$p^k$,其中$n,k$为正整数，$p$为质数，则有$\phi (n)=p^k-p^{k-1}$
2. 设$n,m$为正整数，$gcd(n,m)$=1，则有$\phi (nm)=\phi (n)\ast \phi (m)$

如何计算$\phi (n)$呢？请看：$$\phi (n)=n\ast \sum _{i=1}^n(1-\frac{1}{p_i})$$
用代码实现即为：

long long ans=n;
for (int i=2;i<=sqrt(n);i++) {//寻找因数
   	if (n%i==0) n/=i,ans=ans/i*(i-1);//这里做去分母处理，否则会因精度问题WA
    while (n%i==0) n/=i;//除尽此因数
	if (n>1) {//计算时有可能会出现一个未除的m的质因子，出现m>1 ,说明还剩一个质因子没除
		ans=ans/n*(n-1);
	}
	cout << ans << endl;	
}

现在，切入正题~

当然，只有欧拉函数是不足以解这题的，还要用到关于$gcd$的两个定理：

1. $\forall n,m\in \mathrm{N},m\le n,gcd(n,m)=gcd(m,n-m)=gcd(n,n-m)(更相减损术)$
2. $\forall n,m\in \mathrm{N}$,设$gcd(n,m)=k$，$gcd$ ( $\frac{n}{k}$,$\frac{m}{k}$) $=$ $1$

开始推导：
$$设gcd(a,m)=gcd(a+x,m)=k$$
$$则gcd(\frac{a+x}{k},\frac{m}{k})=1$$
$$分以下两种情况讨论：$$
$1.当\frac{a+x}{k}<\frac{m}{k}时:$
$$则求[\frac{a}{k},\frac{m}{k})这个区间内与\frac{m}{k}互质的数$$
$2.当\frac{a+x}{k}>\frac{m}{k}时:$
$$\because gcd(\frac{a+x}{k},\frac{m}{k})=1$$
$$\therefore gcd(\frac{a+x-m}{k},\frac{m}{k})=1$$
$$则求[0,\frac{a}{k})这个区间内与\frac{m}{k}互质的数$$
$$结合以上两种情况知：即求[0,\frac{m}{k})这个区间内与\frac{m}{k}互质的数$$
$$即求\phi (\frac{m}{k})$$
$$推导完毕$$
现在，我们通过式子变形，明确了我们解决该题的方法。那么，问题就很简单了。这道看似无从下手的题，转化成了求一个欧拉函数的问题。
好了，上代码，解释都在代码里：

#include <bits/stdc++.h>
using namespace std;
int t;
long long a, m;
int main() {
    cin >> t;
    while (t--) {
        scanf("%lld%lld",&a,&m);
        long long k = __gcd(a, m);//gcd函数
        m/=k;//除去最大公约数
        long long ans=m;//记得开long long
		for (int i=2;i<=sqrt(m);i++) {//欧拉函数模板
   			if (m%i==0) m/=i,ans=ans/i*(i-1);
        	while (m%i==0) m/=i;
		}
		if (m>1) {
			ans=ans/m*(m-1);
		}
		cout << ans << endl;	
    }
    return 0;
}

完结撒花……（等我先总个结）

总结

说实话，我在模拟赛做这题时，真的很懵，后来也是推导了很久才想出正解（蒻）。这题考验选手的知识储备，思维能力以及熟练运用知识的能力，对码力要求其实并不高，是一道数论好题。这题也可以用其他方法解，比如莫比乌斯反演，在我接下来的文章可能也会提到。最后，祝大家（当然也包括本蒟蒻）CSP RP++！
（再等等）
大家觉得CSP各题会出什么样的算法呢？（求各路大佬为本蒟蒻指点迷津qwq）