题目描述
欧拉函数
样例
blablabla
算法1
欧拉函数,快速幂
时间复杂度
log n
C++ 代码
/*
注意点:
1.目的是对结果取模,所以有个坑:a=998244353,b=1.如果每步都取模的话,那么这个结果就是0,但结果不是0,
所以为了每步取模,防止结果不同,需要为num先存一个a,所以是a,b-1传入函数.
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int addnum(int a,int b)//快速幂log n
{
int ans=1;
while(b)
{
if(b&1)//**位运算**与b的末尾与1异或,判断是不是一
{
ans = ans * a % mod;
}
b>>=1;
a = a * a % mod;
}
return ans;
}
signed main()
{
//输入
int a,b;
cin>>a>>b;
//运算
if(a==1)//特判:如果a=1,那么num=a^b=1,定义是除了1和本身没有公约数,所以1的结果是0;不特判的话是1
{ //b-1=0,ans返回的是1,num=1,不进入循环,结果便是1
cout<<0<<endl;
return 0;
}
int num=a;
num *= addnum(a,b-1);
for(int i=2;i<=sqrt(a);i++)
{
if(a%i==0)
{
num = num/i*(i-1);//欧拉函数=N*累乘(1-1/i),防止整数1/i变为0,用N*累乘(i-1)/i.
while(a%i==0)
{
a /= i;
}
}
}
//输出(如果到最后没有除干净,便将a再运算一次,后%mod输出)
if(a!=1) num = num/a*(a-1);
cout<<num%mod<<endl;
}