結果

問題 No.1514 Squared Matching
コンテスト
ユーザー vjudge1
提出日時 2025-07-07 11:48:14
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 559 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,115 ms
コンパイル使用メモリ 282,544 KB
実行使用メモリ 729,488 KB
最終ジャッジ日時 2025-07-07 11:48:24
合計ジャッジ時間 8,534 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i,a,b) for(ll i=a;i<=b;i++)

const ll N = 5e7+5;
ll n;
unordered_map<ll, ll> cnt;

int main() {
    cin >> n;
    vector<ll> minp(n+1);
    fo(i,2,n) if(!minp[i])
        for(ll j=i;j<=n;j+=i) if(!minp[j]) minp[j]=i;
    fo(x,1,n) {
        ll y=x, sf=1;
        while(y>1) {
            ll p=minp[y], e=0;
            while(y%p==0) y/=p, e^=1;
            if(e) sf*=p;
        }
        cnt[sf]++;
    }
    ll ans=0;
    for(auto &[k,v]:cnt) ans+=v*v;
    cout << ans << '\n';
}
0