結果

問題 No.3403 Count 1210 Sequence
コンテスト
ユーザー norioc
提出日時 2025-12-10 04:09:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,290 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 303 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 88,516 KB
最終ジャッジ日時 2025-12-10 04:09:53
合計ジャッジ時間 19,483 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 7 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def divisors(n: int) -> list[int]:
    """n の約数を求める"""
    s = set()
    p = 1
    while p * p <= n:
        if n % p == 0:
            s.add(p)
            s.add(n // p)
        p += 1
    return sorted(s)


class ModComb:
    def __init__(self, n: int, mod: int):
        fact = [0] * (n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = i * fact[i-1] % mod

        ifact = [0] * (n+1)
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i] * i % mod
        self.fact = fact
        self.ifact = ifact
        self.mod = mod

    def __call__(self, n: int, k: int) -> int:
        if n < 0 or k > n: return 0
        return (self.fact[n] * self.ifact[k] % self.mod) * self.ifact[n-k] % self.mod


def solve():
    N, A = map(int, input().split())

    res = 0
    for d in divisors(A):
        m = A // d
        if m > N-1: continue
        if (N-1-m) % 2 != 0: continue

        up = (N-1 + m) // 2
        bad_k = up - 1 - m
        tot = mcomb(N-1, up)
        bad = mcomb(N-1, bad_k) if bad_k >= 0 else 0

        res += tot - bad
        res %= MOD

    return res


MOD = 998244353
T = int(input())

mcomb = ModComb(202500, MOD)
for _ in range(T):
    ans = solve()
    print(ans)
0