关于#java#的问题：采用欧拉函数+快速幂来解题，感觉自己写得没错（相关搜索：互质数）

Question

写下面的题，采用欧拉函数+快速幂来解题，感觉自己写得没错，就是通过不了。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        long a = scan.nextLong();
        long b = scan.nextLong();
        long p = 998244353;
        long res = qmi(a,b,p);
        
        //欧拉函数
        long ans = res;
        for(long i = 2; i <= res / i; i++) {
            if(res % i == 0) {
                ans = ans / i * (i-1);
                while(res % i == 0) {
                    res /= i;
                }
            }
        }
        if(res > 1) {
            ans = ans / res * (res-1);
        }
        System.out.println(ans);
        
        scan.close();
    }
    
    //快速幂
    public static long qmi(long a, long b, long p) {
        long res = 1;
        while(b > 0) {
            if(b % 2 != 0) {
                res = res * a % p;
            }
            a = a * a % p;
            b /= 2;
        }
        return res;
    }
}

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

【解题思路】：使用欧拉函数φ(n)计算互质数的个数，结合快速幂算法求解。