第十四届蓝桥杯JavaA组省赛真题 - 互质数的个数

本文主要是介绍第十四届蓝桥杯JavaA组省赛真题 - 互质数的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解题思路：

快速幂 + 欧拉函数

快速幂比较常见于数据较大的取模场景，欧拉函数感觉还是有点抽象

注意：

取模的时候就不要简写了，例如：res = res * a % mod;不要写成res *= a % mod;

import java.util.Scanner;public class Main {static int mod = 998244353;public static void main(String[] args) {Scanner sc = new Scanner(System.in);long a = sc.nextLong();long b = sc.nextLong();// 如果a等于1，则直接输出0，因为任何数的0次方都是1if (a == 1) System.out.println(0);// 初始化结果res为along res = a, x = a;// 循环，从2开始到x的平方根，检查x的因子for (int i = 2; i <= Math.sqrt(x); i++) {// 如果i是x的因子if (x % i == 0) {// 不断除以i，直到x不能被i整除while (x % i == 0) x /= i;// 根据欧拉定理，将res中所有i的因子替换为i-1res = res / i * (i - 1);}}// 如果x还有大于1的因子，重复上述操作if (x > 1) res = res / x * (x - 1);// 输出结果，为res乘以a的b-1次方，并对mod取模System.out.println(res * qmi(a, b - 1) % mod);}// 快速幂运算方法，用于计算a的b次方模mod的值private static long qmi(long a, long b) {long res = 1;while (b > 0) {if ((b % 2) == 1) res = res * a % mod;a = a * a % mod;b /= 2;}return res % mod;}
}

这篇关于第十四届蓝桥杯JavaA组省赛真题 - 互质数的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---