题目描述
给定 a,b
,求 1≤x<ab
中有多少个 x
与 ab
互质。
由于答案可能很大,你只需要输出答案对 998244353
取模的结果。
输入格式
输入一行包含两个整数分别表示 a,b
,用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 30%
的评测用例,ab≤106
;
对于 70%
的评测用例,a≤106
,b≤109
;
对于所有评测用例,1≤a≤109
,1≤b≤1018
。
算法1
二分快速幂 + eular
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
ll f(ll a, ll b, ll c) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % c;
a = a * a % c;
b >>= 1;
}
return ans;
}
ll eular(ll a) {
ll ans = a;
int i;
for (i = 2; i <= a / i; ++i) {
if (a % i == 0) {
ans = ans / i * (i - 1);
while (a % i == 0) a /= i;
}
}
if (a > 1) ans = ans / a * (a - 1);
return ans;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
ll a, b;
cin >> a >> b;
if (a == 1) cout << 0 << '\n';
else cout << eular(a) * f(a, b - 1, mod) % mod << '\n';
}