結果

問題 No.1514 Squared Matching
コンテスト
ユーザー vjudge1
提出日時 2025-07-07 11:31:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,311 bytes
コンパイル時間 3,642 ms
コンパイル使用メモリ 286,848 KB
実行使用メモリ 814,696 KB
最終ジャッジ日時 2025-07-07 11:32:05
合計ジャッジ時間 12,725 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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, a[maxn], 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;
    fo(i, 1, n) a[i]=i;
    sang();
    fo(i, 1, n){
        d[solve(a[i])]++;
    }
    lop(x, d){
        ans+=x.se*(x.se-1)/2;
    }
    cout << ans*2+n;
    return 0;
}
0