互质数的个数（寒假每日一题+欧拉和快速幂）

题目

给定?a,b，求?1≤x<a^b中有多少个?x?与?a^b 互质。

由于答案可能很大，你只需要输出答案对?998244353取模的结果。

输入格式

输入一行包含两个整数分别表示?a,b，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于?30%?的评测用例，ab≤10^6；
对于?70%?的评测用例，a≤10^6，b≤10^9；
对于所有评测用例，1≤a≤10^9，1≤b≤10^18。

样例

输入样例1：

2 5

输出样例1：

16

输入样例2：

12 7

输出样例2：

11943936

题目思路

从题目出发去一个数的互质数数量，我们就可以想到欧拉函数：小于或等于n的正整数中的与n互质的数的数目，其公式较为复杂，我以一个实例来说明：

求x的欧拉函数即将x分解成由其质因数组成的

（x=q1^c1*q2^c2*q3^c3...）

这样欧拉函数：f(x)=x*(1-1/q1)*(1-1/q2)*(1-1/q3)....，

这便是欧拉函数。那么知道这一个定理便可以很快解决该问题。

因为a^b太大，我们可以转化为a*a^(b-1)，这样我们便可以先求出f(a)，f(a^b)=a^(b-1)*f(a)

更加题目要求，我们需要mod一个数，那么求a^(b-1)%MOD便可以使用快速幂，在logb-1的时间复杂度下求出。

源代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MOD = 998244353;

LL a,b;

//快速幂
LL qumi(LL a,LL k){
    
    LL res=1%MOD;
    while(k){
        if(k&1) res = res*a % MOD;
        a=a*a % MOD;
        k>>=1;
    }
    
    return res;
}

 
int main()
{
    cin >> a >> b;
    
    LL sum=a,x=a;
    
    if(a==1){
        cout << 0 << endl;
        return 0;
    }
    
    //求a的欧拉函数
    for(int i=2;i<=a/i;i++){
        if(a%i==0){
            sum=sum/i*(i-1);
            while(a%i==0) a/=i;
        }

    }
    if(a>1) sum=sum/a*(a-1);
    
    //其中a^b=a*a^b-1
    cout << (sum*qumi(x,b-1)) % MOD<< endl;
    return 0;
}