AcWing 4968. 互质数的个数
原题链接
中等
看似套模板,其实还是需要做一些小小的数学变形
import java.util.*;
public class Main {
static final int mod = 998244353;
private static long qmi(long a, long k, int p) {
long res = 1;
while (k != 0) {
if ((k & 1) != 0) res = res * a % p;
k >>= 1;
a = a * a % p;
}
return res;
}
private static long euler(long x) {
long res = x;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
while (x % i == 0) x /= i;
res = res / i * (i - 1);
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
if (a == 1) System.out.println(0);
else System.out.println(qmi(a, b - 1, mod) * euler(a) % mod);
}
}
补充2:由于a = p1^c1p2^c2.....pk^ck,所以a^b = (p1^c1p2^c2.....pk^ck) ^ b,分配给每一项就得到了a^b分解质因数的表达式
加一句:a = 1时特判