結果
問題 | No.3022 一元一次式 mod 1000000000 |
ユーザー |
|
提出日時 | 2025-02-14 22:25:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 301 ms / 2,000 ms |
コード長 | 1,342 bytes |
コンパイル時間 | 207 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 90,680 KB |
最終ジャッジ日時 | 2025-02-17 12:57:09 |
合計ジャッジ時間 | 4,613 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random def extended_euclid(a, b): if b == 0: return (1, 0) else: xd, yd = extended_euclid(b, a % b) return (yd, xd - a // b * yd) input = sys.stdin.readline #sys.setrecursionlimit(10**9) t = int(input()) #alist = list(map(int,input().split())) #alist = [] #s = input() #n,m = map(int,input().split()) #for i in range(n): # alist.append(list(map(int,input().split()))) a = 2**9 b = 5**9 for i in range(t): n,m = map(int,input().split()) if m % 1000000000 == 0: ans = 1 while n % a != 0: ans *= 2 n *= 2 while n % b != 0: ans *= 5 n *= 5 print(ans) continue n %= 1000000000 m %= 1000000000 if n % 2 == 0 or n % 5 == 0: d = math.gcd(n,1000000000) if m % d == 0: x = extended_euclid(n // d,1000000000// d)[0] x %= 1000000000 // d x += 1000000000 // d x %= 1000000000 // d m = (-(m) // d) % (1000000000 // d) print((x * m) % (1000000000 //d)) else: print(-1) continue x = extended_euclid(n,1000000000)[0] ans = x*(-m) % 1000000000 if ans == 0: ans = 1000000000 print(ans)