結果

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

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline


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


divs = [[] for _ in range(203000)]
for d in range(1, 203000):
    for k in range(d, 203000, d):
        divs[k].append(d)


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

    res = 0
    for d in divs[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(2100, MOD)
for _ in range(T):
    ans = solve()
    print(ans)
0