蓝桥杯2023年第十四届省赛真题-互质数的个数
时间限制: 2s 内存限制: 320MB 提交: 3317 解决: 336
题目描述
给定 a, b，求 1 ≤ x < ab 中有多少个 x 与 ab 互质。由于答案可能很大，你只需要输出答案对 998244353 取模的结果。
输入格式
输入一行包含两个整数分别表示 a, b，用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入复制
2 5
样例输出复制
16
提示
对于 30% 的评测用例，ab ≤ 106 ；
对于 70% 的评测用例，a ≤ 106，b ≤ 109 ；
对于所有评测用例，1 ≤ a ≤ 109，1 ≤ b ≤ 1018 。

1.分析

        1.考察欧拉函数和快速幂。

        很奇怪，先计算快速幂再计算欧拉数就正确，反过来就不行。

2.代码

#include<iostream>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL a, b;
LL fmi(LL x, LL y) {      //快速幂
    LL re = 1;
    while (y) {
        if ((y&1)==1) re = re * x%mod;
        y = y >> 1;
        x = x * x % mod;
    }
    return re;
}
int main() {
    cin >> a >> b;
    LL t = fmi(a, b);            //先计算快速幂
    LL num =t;
    for (LL i = 2; i <= t/i; i++) {     //再算欧拉数
        if (t % i == 0) {
            num =  num / i*(i-1)%mod;
            while (t % i == 0) {
                t /= i;
            }
        }
    }
    if(t>1) num = num / t*(t-1)%mod;
    cout << num << endl;
    return 0;
}