Codeforces Round #326 (Div. 2)

B. Duff in Love

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

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

output

input

output

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.

/* ***********************************************

Author        :pk28

Created Time  :2015/10/16 0:38:50

File Name     :cf326B.cpp

************************************************ */

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <iomanip>

#include <list>

#include <deque>

#include <stack>

#include<time.h>

#define ull unsigned long long

#define ll long long

#define INF 0x3f3f3f3f

#define maxn 10000+10

#define cle(a) memset(a,0,sizeof(a))

const ull inf = 1LL << ;

const double eps=1e-;

using namespace std;

bool cmp(int a,int b){

    return a>b;

}

const int S=;//随机算法判定次数，S越大，判错概率越小

//计算 (a*b)%c.   a,b都是long long的数，直接相乘可能溢出的

//  a,b,c <2^63

long long mult_mod(long long a,long long b,long long c)

{

    a%=c;

    b%=c;

    long long ret=;

    while(b)

    {

        if(b&){ret+=a;ret%=c;}

        a<<=;

        if(a>=c)a%=c;

        b>>=;

    }

    return ret;

}

long long pow_mod(ll x,ll n,ll mod)

{

    if(n==)return x%mod;

    x%=mod;

    long long tmp=x;

    long long ret=;

    while(n)

    {

        if(n&) ret=mult_mod(ret,tmp,mod);

        tmp=mult_mod(tmp,tmp,mod);

        n>>=;

    }

    return ret;

}

//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数

//一定是合数返回true,不一定返回false

bool check(long long a,long long n,long long x,long long t)

{

    long long ret=pow_mod(a,x,n);

    long long last=ret;

    for(int i=;i<=t;i++)

    {

        ret=mult_mod(ret,ret,n);

        if(ret==&&last!=&&last!=n-) return true;//合数

        last=ret;

    }

    if(ret!=) return true;

    return false;

}

// Miller_Rabin()算法素数判定

//是素数返回true.(可能是伪素数，但概率极小)

//合数返回false;

bool Miller_Rabin(long long n)

{

    if(n<)return false;

    if(n==)return true;

    if((n&)==) return false;//偶数

    long long x=n-;

    long long t=;

    while((x&)==){x>>=;t++;}

    for(int i=;i<S;i++)

    {

        long long a=rand()%(n-)+;//rand()需要stdlib.h头文件

        if(check(a,n,x,t))

            return false;//合数

    }

    return true;

}

long long factor[];//质因数分解结果（刚返回时是无序的）

int tol;//质因数的个数。数组小标从0开始

long long gcd(long long a,long long b)

{

    if(a==)return ;//???????

    if(a<) return gcd(-a,b);

    while(b)

    {

        long long t=a%b;

        a=b;

        b=t;

    }

    return a;

}

long long Pollard_rho(long long x,long long c)

{

    long long i=,k=;

    long long x0=rand()%x;

    long long y=x0;

    while()

    {

        i++;

        x0=(mult_mod(x0,x0,x)+c)%x;

        long long d=gcd(y-x0,x);

        if(d!=&&d!=x) return d;

        if(y==x0) return x;

        if(i==k){y=x0;k+=k;}

    }

}

//对n进行素因子分解

void findfac(long long n)

{

    if(Miller_Rabin(n))//素数

    {

        factor[tol++]=n;

        return;

    }

    long long p=n;

    while(p>=n)p=Pollard_rho(p,rand()%(n-)+);

    findfac(p);

    findfac(n/p);

}

map<ll,ll>mp;

int main()

{

    #ifndef ONLINE_JUDGE

    //freopen("in.txt","r",stdin);

    #endif

    //freopen("out.txt","w",stdout);

    ll n;

    while(cin>>n){

        if(n==){

            cout<<<<endl;continue;

        }

        mp.clear();

        tol=;

        findfac(n);

        ll ans=1LL;

        for(int i=;i<tol;i++){

            if(!mp[factor[i]]){

                mp[factor[i]]=;

                ans*=factor[i];

            }

        }

        printf("%I64d\n",ans);

    }

    return ;

}

巴特西

Codeforces Round #326 (Div. 2)

最新文章

热门文章