Codeoforces 558 B. Duff in Love 【 Codeforces Round #326 (Div. 2)】-白红宇

Duff is in love with lovely numbers! A positive integer x is called lovely if and only if there is no such positive integer a > 1 such that a2 is a divisor of x.

$\text{[math]}$

Malek has a number store! In his store, he has only divisors of positive integer n (and he has all of them). As a birthday present, Malek wants to give her a lovely number from his store. He wants this number to be as big as possible.

Malek always had issues in math, so he asked for your help. Please tell him what is the biggest lovely number in his store.

Input

The first and only line of input contains one integer, n (1 ≤ n ≤ 1012).

Output

Print the answer in one line.

           Sample test(s) 
             input 
10
             output 
10
             input 
12
             output 
6

Note

In first sample case, there are numbers 1, 2, 5 and 10 in the shop. 10 isn't divisible by any perfect square, so 10 is lovely.

In second sample case, there are numbers 1, 2, 3, 4, 6 and 12 in the shop. 12 is divisible by 4 = 22, so 12 is not lovely, while 6 is indeedlovely.

题目大意：

给你一个数 n【注意 n 的范围，要用long long】，然后找它所有因子数中没有平方数的最大值

样例解释：

第二个样例：12的因子有1 2 3 4 6 12，又因为12中有 4 = 2*2，所以12舍去，就剩下 6 了，

解题思路:

说穿了，这其实就是一个所有的素因子乘起来的问题，所以我们只需要对 n 进行素因子分解就 ok 了，

上代码：

#include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;#define MM(a) memset(a,0,sizeof(a))typedef long long LL;typedef unsigned long long ULL;const int maxn = 1e7+5;const int mod = 1000000007;const double eps = 1e-7;bool prime[maxn];LL p[maxn],k;///素数筛选void isprime(){ k = 0; MM(prime); for(LL i=2; i
                    
                      1) { fac[cnt] = x; num[cnt++] = 1; }}int main(){ LL n; isprime(); while(cin>>n) { Dec(n); LL ans = 1; for(int i=0; i