結果

問題 No.1514 Squared Matching
コンテスト
ユーザー ああいい
提出日時 2022-03-15 22:13:49
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 738 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 82,832 KB
実行使用メモリ 848,132 KB
最終ジャッジ日時 2024-09-22 14:33:40
合計ジャッジ時間 2,894 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
import sys
if N == 1:
    print(1)
    exit()
if N == 2:
    print(2)
    exit()
    
Sum = [0] * (N + 1)
i = 1
while i * i <= N:
    Sum[i*i] = 1
    i += 1
for i in range(1,N+1):
    Sum[i] += Sum[i-1]
dat = [1] * (N + 1)
era = [0] * (N + 1)
for i in range(2,N+1):
    if era[i] == 0:
        for j in range(2 * i,N+1,i):
            era[j] = 1
        now = i
        count = 1
        while now <= N:
            if count % 2 == 1:
                for j in range(now,N+1,now):
                    dat[j] *= i
            else:
                for j in range(now,N+1,now):
                    dat[j] //= i
            now *= i
            count += 1
ans = 0
for i in range(1,N+1):
    ans += Sum[N//dat[i]]
print(ans)
0