[ABC254D] Together Square--分解质因数。

[ABC254D] Together Square - 洛谷

 

#include <bits/stdc++.h>
#define int long long //(有超时风险)
#define PII pair<int,int>
#define endl '\n'

using namespace std;

const int N=2e5+10,M=1e3+10;

int a[N],pre[N];

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n;cin>>n;

    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int x=i;
        map<int,int>mp;

        for(int j=2;j<=i/j;j++)
        {
            if(x%j==0)
            {
                while(x%j==0)
                {
                    mp[j]++;
                    x/=j;
                }
            }
        }
        if(x>1)
            mp[x]++;

        int tmp=1;
        for(auto i:mp)
            if(i.second%2==1)
                tmp*=i.first;
        //因为枚举i，与其它所有数配对，那么排除自身的奇数的情况，剩下的全是偶数。
        cnt+=sqrt(n/tmp);
    }

    cout<<cnt<<endl;
    return 0;
}