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

发布时间:2024年01月14日

题目

给定?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;
}

文章来源:https://blog.csdn.net/a18173352623/article/details/135562904
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。