結果
問題 | No.2947 Sing a Song |
ユーザー |
|
提出日時 | 2024-10-25 21:47:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 110 ms / 2,000 ms |
コード長 | 1,182 bytes |
コンパイル時間 | 396 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 80,324 KB |
最終ジャッジ日時 | 2024-10-25 21:47:49 |
合計ジャッジ時間 | 4,904 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
# https://ikatakos.com/pot/programming_algorithm/number_theory/euclidean_algorithm # 引用(もといパクリ) # Python で RSA 公開鍵暗号をなぞってみる - CAMPHOR- Tech Blog # https://tech.camph.net/rsa-public-key-encryption/ def ex_euclid(x, y): c0, c1 = x, y a0, a1 = 1, 0 b0, b1 = 0, 1 while c1 != 0: m = c0 % c1 q = c0 // c1 c0, c1 = c1, m a0, a1 = a1, (a0 - q * a1) b0, b1 = b1, (b0 - q * b1) return c0, a0, b0 def exex_euclid(x,y,z): c, a, b = ex_euclid(x, y) w, m = divmod(z, c) # zがcの倍数でないなら等式は不可能 if m != 0: return None u, v = x // c, y // c a, b = a * w, b * w # aを非負数の中で最小にする f, a = divmod(a, v) b += u * f # aを最小にしたのにbが負なら、ともに正の組は不可能 if b < 0: return None return c, a, b, u, v import sys input = sys.stdin.readline N = int(input()) S, T = input().split() A = list(map(int, input().split())) y = len(S) x = len(T) for z in A: c, a, b, u, v = exex_euclid(x, y, z) print(*([S]*b), *([T]*a))