题意
题目链接
分析
sπo yyb
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
int x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 2e5 + 7, mod = 998244353;
int n, m, k, pc;
LL fac[N], inv[N], invfac[N];
int phi[N], low[N], pri[N];
void sieve(int n) {
phi[1] = 1;int to;
for(int i = 2; i <= n; ++i) {
if(!low[i]) low[i] = i, phi[i] = i - 1, pri[++pc] = i;
for(int j = 1; j <= pc && (to = i * pri[j]) <= n; ++j) {
low[to] = pri[j];
if(i % pri[j] == 0) {
phi[to] = phi[i] * pri[j];
break;
}
phi[to] = phi[i] * (pri[j] - 1);
}
}
}
LL C(int n, int m) {
return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
void add(LL &a, LL b) {
a += b;
if(a >= mod) a -= mod;
}
LL put(int a, int b) {
if(!b) return 0;
LL res = 0;
for(int i = 0; i <= a / (k + 1); ++i)
add(res, (i & 1 ? mod - 1 : 1) * C(b, i) % mod * C(a - i * (k + 1) + b - 1, b - 1) % mod);
return res;
}
LL solve(int d) {
int c = m / (n / d); LL res = 0;
if(c <= k) return C(d, c);
for(int i = 0; i <= k; ++i)
add(res, (i + 1) * put(c - i, d - c - 1) % mod);
return res;
}
int main() {
n = gi(), m = gi(), k = gi();
if(n == m)
return puts(k < m ? "0" : "1"), 0;
sieve(n);
inv[1] = fac[0] = invfac[0] = 1;
rep(i, 1, 2 * n) {
if(i ^ 1) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
fac[i] = fac[i - 1] * i % mod;
invfac[i] = invfac[i - 1] * inv[i] % mod;
}
LL ans = 0;
for(int i = 1; i <= n; ++i) if(n % i == 0 && m % (n / i) == 0)
add(ans, solve(i) * phi[n / i] % mod);
printf("%lld
", ans * inv[n] % mod);
return 0;
}