結果
問題 |
No.1022 Power Equation
|
ユーザー |
![]() |
提出日時 | 2020-11-21 13:44:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 229 ms / 2,000 ms |
コード長 | 872 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 80,404 KB |
最終ジャッジ日時 | 2024-07-23 15:36:32 |
合計ジャッジ時間 | 1,903 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 8 |
ソースコード
import sys from math import gcd def I(): return int(sys.stdin.readline().rstrip()) def lcm(a,b): return a*b//gcd(a,b) def f(N): res = 2*N**2-N M = int(N**.5) flag = [1]*(M+1) # flag[i] == 1 ⇔ iが冪乗数でない for i in range(2,M+1): if flag[i] == 0: continue x = i**2 while x <= M: flag[x] = 0 x *= i for a in range(2,M+1): if flag[a] == 0: continue e = 2 while a**e <= N: res += 2*(N//e) e += 1 for aa in range(2,M+1): if flag[aa] == 0: continue m = 2 while aa**m <= N: e = m+1 while aa**e <= N: res += 2*(N*m//lcm(m,e)) e += 1 m += 1 return res T = I() for _ in range(T): N = I() print(f(N))