結果
問題 | No.1747 Many Formulae 2 |
ユーザー |
|
提出日時 | 2021-11-19 22:32:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 790 bytes |
コンパイル時間 | 386 ms |
コンパイル使用メモリ | 82,312 KB |
実行使用メモリ | 77,568 KB |
最終ジャッジ日時 | 2025-01-01 19:25:10 |
合計ジャッジ時間 | 2,081 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
from math import gcd import random from collections import defaultdict def is_prime(n): if n==2: return True if n==1 or n&1==0: return False d=(n-1)>>1 while d&1==0: d>>=1 for k in range(100): a=random.randint(1,n-1) t=d y=pow(a, t, n) while t!=n-1 and y!=1 and y!=n-1: y=(y*y)%n t<<=1 if y!=n-1 and t&1==0: return False return True s = list(input()) ans = 0 for i in range(2 ** (len(s) - 1)): x = 0 now = int(s[0]) for j in range(len(s) - 1): if 1 & (i >> j): x += now now = int(s[j + 1]) else: now = 10 * now + int(s[j + 1]) x += now now = 0 if is_prime(x): ans += 1 print(ans)