結果
問題 | No.1514 Squared Matching |
ユーザー |
![]() |
提出日時 | 2021-05-21 23:15:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,441 ms / 4,000 ms |
コード長 | 993 bytes |
コンパイル時間 | 1,760 ms |
コンパイル使用メモリ | 192,320 KB |
最終ジャッジ日時 | 2025-01-21 16:41:27 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; bool prime[50000005]; int tmp[50000005],sum[50000005]; int main() { int N; cin >> N; memset(prime,true,sizeof(prime)); prime[0] = false; prime[1] = false; for(int i = 2; i <= 50000000; i++) { if(!prime[i]) { continue; } for(int j = i*2; j <= 50000000; j += i) { prime[j] = false; } } for(int i = 1; i <= 50000000; i++) { tmp[i] = i; } for(int i = 2; i*i <= 50000000; i++) { if(!prime[i]) { continue; } for(int j = i*i; j <= 50000000; j += i*i) { while (tmp[j]%(i*i) == 0) { tmp[j] /= i*i; } } } for(int i = 1; i*i <= 50000000; i++) { sum[i*i]++; } for(int i = 1; i <= 50000000; i++) { sum[i+1] += sum[i]; } int ans = 0; for(int i = 1; i <= N; i++) { ans += sum[N/tmp[i]]; } cout << ans << endl; }