AcWing 4968. 互质数的个数(欧拉函数求互质数)
原题链接
中等
作者:
半透明の微笑
,
2024-04-07 19:43:00
,
所有人可见
,
阅读 7
import java.io.*;
public class Main{
static int MOD = 998244353;
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
long a = Long.parseLong(s1[0]);
long b = Long.parseLong(s1[1]);
if(a == 1){
System.out.println(0);
return;
}
long res = a;
long x = a;
//欧拉函数求互质数
for(int i = 2; i * i <= res; i ++){
if(x % i == 0){//!!别漏掉
while(x % i == 0) x /= i;
res = (res * (i - 1) / i) % MOD;
}
}
if(x != 1) res = (res * (x - 1) / x) % MOD;
res = (qmi(a, b - 1, MOD) * res) % MOD;
System.out.println(res);
}
static long qmi(long a, long k, int p){
long res = 1;
while(k != 0){
if((k & 1) == 1){
res = (res * a) % p;
}
k >>= 1;
a = (a * a % p);
}
return res;
}
}