結果

問題 No.2324 Two Countries within UEC
ユーザー moharan627
提出日時 2023-05-28 15:29:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 236 ms / 2,000 ms
コード長 2,142 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 79,960 KB
最終ジャッジ日時 2024-06-26 23:25:51
合計ジャッジ時間 8,055 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
#sys.setrecursionlimit(10 ** 6)
INF = float('inf')
#10**20,2**63
MOD = 10**9 + 7
MOD2 = 998244353
from collections import defaultdict
def ceil(A,B):
return -(-A//B)
def inv_gcd(a, b):
a = a % b
if a == 0:
return (b, 0)
s = b;
t = a
m0 = 0;
m1 = 1
while (t):
u = s // t
s -= t * u
m0 -= m1 * u
s, t = t, s
m0, m1 = m1, m0
if m0 < 0:
m0 += b // s
return (s, m0)
def inv_mod(x, m):
assert 1 <= m
z = inv_gcd(x, m)
assert z[0] == 1
return z[1]
def crt(r, m):
assert len(r) == len(m)
n = len(r)
r0 = 0;
m0 = 1
for i in range(n):
assert 1 <= m[i]
r1 = r[i] % m[i]
m1 = m[i]
if m0 < m1:
r0, r1 = r1, r0
m0, m1 = m1, m0
if (m0 % m1 == 0):
if (r0 % m1 != r1):
return (0, -1)
continue
g, im = inv_gcd(m0, m1)
u1 = m1 // g
if ((r1 - r0) % g):
return (0, -1)
x = (r1 - r0) // g % u1 * im % u1
r0 += x * m0
m0 *= u1
if r0 < 0:
r0 += m0
return (r0, m0)
def solve():
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LC(): return list(input())
def IC(): return [int(c) for c in input()]
def MI(): return map(int, sys.stdin.readline().split())
N,M,P,Q = MI()
import math
for q in range(Q):
X,F = MI()
X%=P
if(X==0):
if(F==0):
print(M)
else:
print(0)
continue
G = math.gcd(X,P)
#G<=P
#print(G)
r,m=crt([F,0],[P,X])
if (m == -1):
print(0)
continue
period = P//G
# G<=P
#
ans = M//period
rest_m = M%period
#print("R:",r,"M:",m)
if(r==0):
r+=m
#print(r//X,rest_m)
if(r//X<=rest_m):
print(ans+1)
else:
print(ans)
return
solve()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0