Codeforces Round #326 (Div. 2) B. Duff in Love 分解质因数-白红宇

Codeforces Round #326 (Div. 2) B. Duff in Love 分解质因数

阅读量：5825 次

发布时间：2019-06-18

本文共 3153 字，大约阅读时间需要 10 分钟。

B. Duff in Love

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/588/problem/B

Description

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 Input

Sample Output

HINT

题意

给你一个数p，然后让你找到一个最大的数x，要求满足这个x是p的因子，并且p的因子中没有平方数

题解：

对于这个数p，我们进行质因数分解就好了，分解之后，每一个质因数都只选择一个就行了

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 110#define eps 1e-9int Num;//const int inf=0x7fffffff; //§ß§é§à§é¨f§3const int inf=0x3f3f3f3f;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//**************************************************************************************//****************************************************************// Miller_Rabin 算法进行素数测试//速度快，而且可以判断 <2^63的数//****************************************************************const int S=20;//随机算法判定次数，S越大，判错概率越小//计算 (a*b)%c. a,b都是long long的数，直接相乘可能溢出的// a,b,c <2^63long long mult_mod(long long a,long long b,long long c){ a%=c; b%=c; long long ret=0; while(b) { if(b&1){ret+=a;ret%=c;} a<<=1; if(a>=c)a%=c; b>>=1; } return ret;}//计算 x^n %clong long pow_mod(long long x,long long n,long long mod)//x^n%c{ if(n==1)return x%mod; x%=mod; long long tmp=x; long long ret=1; while(n) { if(n&1) ret=mult_mod(ret,tmp,mod); tmp=mult_mod(tmp,tmp,mod); n>>=1; } return ret;}//以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数//一定是合数返回true,不一定返回falsebool 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=1;i<=t;i++) { ret=mult_mod(ret,ret,n); if(ret==1&&last!=1&&last!=n-1) return true;//合数 last=ret; } if(ret!=1) return true; return false;}// Miller_Rabin()算法素数判定//是素数返回true.(可能是伪素数，但概率极小)//合数返回false;bool Miller_Rabin(long long n){ if(n<2)return false; if(n==2)return true; if((n&1)==0) return false;//偶数 long long x=n-1; long long t=0; while((x&1)==0){x>>=1;t++;} for(int i=0;i
                    
                     D;int tot=0;void findfac(long long n){ if(Miller_Rabin(n))//素数 { D.push_back(n); return; } long long p=n; while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1); findfac(p); findfac(n/p);}//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&int main(){ ll x; cin>>x; if(x==1LL) { cout<<"1"<

转载地址：http://elidx.baihongyu.com/

你可能感兴趣的文章

GitHub宣布推出Electron 1.0和Devtron，并将提供无限制的私有代码库