結果
問題 | No.2929 Miracle Branch |
ユーザー |
|
提出日時 | 2024-10-12 15:57:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 310 ms / 2,000 ms |
コード長 | 1,403 bytes |
コンパイル時間 | 179 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 96,512 KB |
最終ジャッジ日時 | 2024-10-12 15:58:13 |
合計ジャッジ時間 | 16,577 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
def MillerRabin_64bit(x): if x <= 1: return False if x == 2: return True if x % 2 == 0: return False if x < 1 << 30: test = [2, 7, 61] else: test = [2,325,9375,28178,450775,9780504,1795265022] s = 0 d = x - 1 while d & 1 == 0: s += 1 d >>= 1 for i in test: if x <= i: return True y = pow(i,d,x) if y == 1 or y == x - 1: continue c = 0 for j in range(s-1): y = y * y % x if y == x - 1: c = 1 break if not c: return False return True x = int(input()) if x == 1: print(2) print(1,2) print('b g') exit() a = [] z = 0 for i in range(2,2*10**5): if MillerRabin_64bit(i) == False: continue while x % i == 0: if i == 2: z += 1 else: a.append(i) x //= i if x != 1: exit(print(-1)) ans = 0 while z >= 2: a.append(4) z -= 2 if z == 1: a.append(2) ans = sum(a) + len(a) if ans > 2*10**5: exit(print(-1)) x = len(a) print(ans) cnt = len(a) for i in range(len(a)): for j in range(a[i]): print(i+1,cnt+1) cnt +=1 for i in range(len(a)-1): print(i+1,i+2) q = [] for i in range(len(a)): q.append('b') for i in range(sum(a)): q.append('g') print(*q)