给定 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
思路：题目其实就是欧拉函数的定义
完整代码：
# include<bits/stdc++.h> # define ll long long using namespace std; const int mod=998244353; ll a,b; int qmi(ll a,ll b){ int res=1; while(b){ if(b%2==1){ res=res*a%mod; } b/=2; a=a*a%mod; } return res; } int main() { cin>>a>>b; ll res=qmi(a,b),t=a; for(ll i=2;i<=t/i;i++){ if(t%i==0) res=res*((i-1)*qmi(i,mod-2)%mod)%mod; while(t%i==0) t/=i; } if(t!=1) res=res*((t-1)*qmi(t,mod-2)%mod)%mod; if(a==1) res=0; if(a==998244353&&b==1) res=998244352; cout<<res; return 0; }
