题意

题目链接

分析

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\n", ans * inv[n] % mod);

	return 0;

}