結果
問題 | No.2249 GCDistance |
ユーザー |
![]() |
提出日時 | 2023-06-29 16:00:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 756 ms / 5,000 ms |
コード長 | 772 bytes |
コンパイル時間 | 345 ms |
コンパイル使用メモリ | 82,068 KB |
実行使用メモリ | 262,928 KB |
最終ジャッジ日時 | 2024-07-06 06:44:26 |
合計ジャッジ時間 | 10,924 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
import sysreadline = sys.stdin.readline#n = int(readline())#*a, = map(int,readline().split())# b = [list(map(int,readline().split())) for _ in range()]def enumerate_tortient(N):primes = []lpf = [0]*(N+1) # least prime factortor = [1]*(N+1); tor[0] = 0for x in range(2,N+1):if lpf[x] == 0:lpf[x] = xprimes.append(x)tor[x] = x-1for p in primes:if p > lpf[x] or x*p > N: breaklpf[x*p] = ptor[x*p] = tor[x]*(p if lpf[x] == p else p-1)return torT = int(readline())N = 10**7tor = enumerate_tortient(N)#print(tor)tor[1] -= 1for i in range(1,N+1):tor[i] += tor[i-1]for _ in range(T):n = int(readline())print(n*(n-1) - tor[n])