专门做宠物食品的网站/快速优化排名公司推荐

题目1 互质数的个数

给定 a,b，求 1≤x<ab 中有多少个 x 与 ab 互质。

由于答案可能很大，你只需要输出答案对 998244353 取模的结果。

输入格式

输入一行包含两个整数分别表示 a,b，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 30% 的评测用例，$ab\le 10^6$；
对于 70% 的评测用例，$a\le 10^6，b\le 10^9$；
对于所有评测用例，$1\le a\le 10^9，1\le b\le 10^{18}$。

输入样例1：

2 5

输出样例1：

16

输入样例2：

12 7

输出样例2：

11943936

思路

1. 主要考察数学知识：欧拉公式求小于x的互质的个数
2. 互质的含义就是：两个数的最大公约数是1
3. 另外注意到数据范围较大，需要利用快速幂or pow(a,b,mod)

python代码

a,b=map(int,input().split())
mod=998244353def eular(x):global modres=xfor i in range(2,int(x**0.5)+1):if x%i==0:while x%i==0:x//=ires=res//i*(i-1)if x>1:res=res//x*(x-1)return resans=1
def fast(a,b):global answhile b>0:if b&1:ans=ans*a%moda=a*a%modb>>=1return ans
ans=fast(a,b-1)*eular(a)%mod
print(ans)

知识点

蓝桥杯笔记：蓝桥杯备赛笔记

1. 欧拉公式
2. 手写快速幂（$10^{18}内数据$）
3. eular(a^b)%mod==a^(b-1)*eular(a)%mod==pow(a,b-1,mod)*(eular(a))