結果

問題 No.8120 Aoki's Present for Takahashi
コンテスト
ユーザー hirayuu_yc
提出日時 2025-04-01 23:04:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 884 ms / 2,000 ms
コード長 2,560 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 88,428 KB
最終ジャッジ日時 2025-04-01 23:11:12
合計ジャッジ時間 14,805 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import typing
def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    a %= b
    if a == 0:
        return (b, 0)

    # Contracts:
    # [1] s - m0 * a = 0 (mod b)
    # [2] t - m1 * a = 0 (mod b)
    # [3] s * |m1| + t * |m0| <= b
    s = b
    t = a
    m0 = 0
    m1 = 1

    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u  # |m1 * u| <= |m1| * s <= b

        # [3]:
        # (s - t * u) * |m1| + t * |m0 - m1 * u|
        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        # = s * |m1| + t * |m0| <= b

        s, t = t, s
        m0, m1 = m1, m0

    # by [3]: |m0| <= b/g
    # by g != b: |m0| < b/g
    if m0 < 0:
        m0 += b // s

    return (s, m0)

def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
    assert len(r) == len(m)

    # Contracts: 0 <= r0 < m0
    r0 = 0
    m0 = 1
    for r1, m1 in zip(r, m):
        assert 1 <= m1
        r1 %= m1
        if m0 < m1:
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue

        # assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

        '''
        (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
        r2 % m0 = r0
        r2 % m1 = r1
        -> (r0 + x*m0) % m1 = r1
        -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
        -> x = (r1 - r0) / g * inv(u0) (mod u1)
        '''

        # im = inv(u0) (mod u1) (0 <= im < u1)
        g, im = _inv_gcd(m0, m1)

        u1 = m1 // g
        # |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
        if (r1 - r0) % g:
            return (0, 0)

        # u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
        x = (r1 - r0) // g % u1 * im % u1

        '''
        |r0| + |m0 * x|
        < m0 + m0 * (u1 - 1)
        = m0 + m0 * m1 / g - m0
        = lcm(m0, m1)
        '''

        r0 += x * m0
        m0 *= u1  # -> lcm(m0, m1)
        if r0 < 0:
            r0 += m0

    return (r0, m0)

P1=443
P2=998243353//443
p1=[1]*300000
cnt=[0]*300000
p2=[1]*300000
for i in range(1,300000):
    p2[i]=(p2[i-1]*i)%P2
    nc=0
    ni=i
    while ni%P1==0:
        ni//=P1
        nc+=1
    cnt[i]=cnt[i-1]+nc
    p1[i]=(p1[i-1]*ni)%P1
t,tau=map(int,input().split())
for i in range(tau):
    N,M=map(int,input().split())
    if i==t-1:
        print(-1)
        continue
    p1a=0
    if cnt[M]-cnt[N]-cnt[M-N]==0:
        p1a=(p1[M]*pow(p1[N],-1,P1)*pow(p1[M-N],-1,P1))%P1
    p2a=(p2[M]*pow(p2[N],-1,P2)*pow(p2[M-N],-1,P2))%P2
    print(crt([p1a,p2a],[P1,P2])[0])
0