結果
問題 |
No.1514 Squared Matching
|
ユーザー |
![]() |
提出日時 | 2025-07-07 12:07:58 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,087 ms / 4,000 ms |
コード長 | 887 bytes |
コンパイル時間 | 3,532 ms |
コンパイル使用メモリ | 275,448 KB |
実行使用メモリ | 443,124 KB |
最終ジャッジ日時 | 2025-07-07 12:08:35 |
合計ジャッジ時間 | 30,355 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
# include <bits/stdc++.h> using namespace std; int n,a[50000005],c[50000005],maxn=5*1e7,res; bool b[50000005]; void sang() { for (int i = 1; i <= maxn; i++) { b[i] = true; a[i] = i; } b[1] = false; for (int i = 2; i <= sqrt(maxn); i++) { if (b[i]) { for (int j = i*i; j <= maxn; j+= i) { b[j] = false; } for (int j = i*i; j <= maxn; j+=i*i) { while (a[j] % (i*i) == 0) { a[j] /= (i*i); } } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; sang(); for (int i = 1; i <= n; i++) { c[a[i]]++; } for (int i = 1; i <= n; i++) { res += (c[i]*c[i]); } cout << res; }