4383: n % ( pow( p , 2) ) ===0 

Time Limit(Common/Java):10000MS/30000MS     Memory Limit:65536KByte

Total Submit: 237            Accepted:54

Description

 

There is a number n , determine whether there is a p (p>1) that p^2 is a divisor of n.

 

Input

 

The first line contains an integer T , the number of test case.

The following T lines , each contains an integer n.

( 1<= T <=10^2 , 1<= n <=10^18 )

 

Output

 

A integer p , if there exist multiple answer ,output the minimum one.

Or print “oh,no.” .

 

Sample Input

 

3

8

16

17

Sample Output

 

2

2

oh,no.

Source

这个题是错了一个数据，最后我去修了这个数据并加强了，好开心

就是问一下一个数是不是一个素数的平方，这个题的思路比较简单，就是一个大数的素数分解，直接搞一个miller_rabin的素数检测，再来一个pollard_rho大数分解质因数就好的

那个判断次数一般选20

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef __int64 ll;const int times=20;const int N=100;ll mult_mod(ll a,ll b,ll mod){ a%=mod; b%=mod; ll res=0; while(b) { if(b&1) { res+=a; res%=mod; } a<<=1; if(a>=mod) a%=mod; b>>=1; } return res;}ll pow_mod(ll x,ll n,ll mod){ if(n==1) return x%mod; x%=mod; ll t=x; ll res=1; while(n) { if(n&1) res=mult_mod(res,t,mod); t=mult_mod(t,t,mod); n>>=1; } return res;}bool test(ll a,ll n,ll x,ll t){ ll res=pow_mod(a,x,n); ll last=res; for(int i=1; i<=t; i++) { res=mult_mod(res,res,n); if(res==1&&last!=1&&last!=n-1) return true; last=res; } if(res!=1) return true; return false;}bool miller_rabin(ll n){ if(n<2) return false; if(n==2) return true; if((n&1)==0) return false; ll x=n-1,t=0; while((x&1)==0) { x>>=1; t++; } for(int i=0; i
           
            =n) p=pollard_rho(p,rand()%(n-1)+1); find_factor(p); find_factor(n/p);}int main(){ srand(time(0)); int t; scanf("%d",&t); ll n; while(t--) { scanf("%I64d",&n); if(miller_rabin(n)||n<=1) { printf("oh,no.\n"); continue; } tot=0; find_factor(n); sort(factor,factor+tot); int f=1; for(int i=1; i