试题 算法训练 素因子去重

    资源限制
    时间限制：1.0s 内存限制：256.0MB
    问题描述
    　　给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1
    输入格式
    　　一个整数，表示n
    输出格式
    　　输出一行，包含一个整数p。
    样例输入
    1000
    样例输出
    10
    数据规模和约定
    　　n<=10^12
    　　样例解释：n=1000=2^3_5_3，p=2*5=10

    1. #include <iostream>
    2. #include <map>
    3. #include <cmath>
    4. typedef long long ll;
    6. using namespace std;
    7. int main() {
    8.     ll n;
    9.     cin >> n;
    11.     map<ll, int> num;
    12.     while (n % 2 == 0) {
    13.         num[2]=1;
    14.         n /= 2;
    15.     }
    16.     for (ll i = 3; i <= sqrt(n * 1.0); i += 2) {
    17.         while (n % i == 0) {
    18.             num[i]=1;
    19.             n /= i;
    20.         }
    21.     }
    22.     if (n > 2) {
    23.         num[n]=1;
    24.     }
    26.     ll ans=1;
    27.     for (map<ll, int>::iterator it = num.begin(); it != num.end(); ++it){
    29.         ans *= it->first;
    31.     }
    33.     cout<<ans;
    35.     return 0;
    36. }

    map、迭代器、