結果

問題 No.1514 Squared Matching
ユーザー vjudge1
提出日時 2025-07-07 11:35:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,275 bytes
コンパイル時間 2,766 ms
コンパイル使用メモリ 288,148 KB
実行使用メモリ 570,916 KB
最終ジャッジ日時 2025-07-07 11:35:53
合計ジャッジ時間 13,075 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
#pragma GCC target("avx")
#pragma GCC optimize("O2")
#pragma GCC optimize("inline")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define fo(i, a, b) for(ll i=a; i<=b; i++)
#define fod(i, a, b) for(ll i=a; i>=b; i--)
#define lop(x, s) for(auto x : s)
#define sz(s) s.size()
#define all(s) s.begin(), s.end()
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
const ll maxn=5e7+5;

ll n, s[maxn], ans=0;
map<vector<pll> , ll> d;

void sang(){
    fo(i, 2, maxn-1){
        if(s[i]==0){
            for(ll j=i; j<maxn; j+=i){
                if(s[j]==0){
                    s[j]=i;
                }
            }
        }
    }
}
vector<pll> solve(ll x){
    vector<pll> res;
    while(x>1){
        ll p=s[x], c=0;
        while(x%p==0){
            x/=p;
            c=c^1;
        }
        if(c) res.push_back(mp(p, 1));
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    sang();
    fo(i, 1, n){
        d[solve(i)]++;
    }
    lop(x, d){
        ans+=x.se*(x.se-1)/2;
    }
    cout << ans*2+n;
    return 0;
}
0