蓝桥3522.互质数的个数

本文主要是介绍蓝桥3522.互质数的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码：

只能对30%

快速幂 求 a b幂

欧拉函数求 互质数个数

欧拉函数：欧拉函数φ(n)的计算及欧拉定理 - 知乎 (zhihu.com)

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {private static long mod = 998244353L;private static long a,b,res;public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...a = scan.nextLong();b = scan.nextLong();long n = qpow(a,b);System.out.println(Euler(n));// System.out.println(Euler(ab)%mod);scan.close();}private static long Euler(long n) {long res = n;for (long i = 2; i * i <= n; i++) {if (n % i == 0) {res = res / i * (i - 1);while (n % i == 0) {n /= i;}res%=mod;}}if (n > 1) {res -= res / n;res%=mod;}return res;}public static long qpow(long a,long n){if(n==0){return 1;}else if(n%2==1){return qpow(a,n-1)*a%mod;}else{long temp = qpow(a,n/2)%mod;return temp*temp%mod;}}private static long Euler_pow(long a, long b) {long ans = 1;while (b > 0) {if ((b & 1) > 0) {ans = ((ans % mod) * (a % mod)) % mod;}a = ((a % mod) * (a % mod)) % mod;b /= 2;}return ans;}
}

这篇关于蓝桥3522.互质数的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---