Spoj SAS002

import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.;
import java.util.
;

public class PollardRho {

``````private final static BigInteger ZERO = new BigInteger("0");
private final static BigInteger ONE  = new BigInteger("1");
private final static BigInteger TWO  = new BigInteger("2");
private final static SecureRandom random = new SecureRandom();

static Vector<BigInteger> v = new Vector<BigInteger>();
static HashMap<Long,Long> m = new HashMap();
public static BigInteger rho(BigInteger N) {

BigInteger divisor;
BigInteger c  = new BigInteger(N.bitLength(), random);
BigInteger x  = new BigInteger(N.bitLength(), random);
BigInteger xx = x;

if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

do {
divisor = x.subtract(xx).gcd(N);
} while((divisor.compareTo(ONE)) == 0);

return divisor;
}
``````

public static long power(long x, long y, long p)
{

``````    long  res = 1;

x = x % p;

while (y > 0)
{

if((y & 1)==1)
res = (res * x) % p;

y = y >> 1;
x = (x * x) % p;
}
return res;
}

public static void factor(BigInteger N) {

if (N.compareTo(ONE) == 0) return;

if (N.isProbablePrime(20)) {
return;
}

BigInteger divisor = rho(N);
factor(divisor);
factor(N.divide(divisor));
}

public static void main(String[] args) throws Exception {
``````

Scanner sc = new Scanner(System.in);
for(int k = 0 ;k < n ;k++)
{

BigInteger N = sc.nextBigInteger();
BigInteger t= new BigInteger(“9223372036854775807”);

int x= N.compareTo(t);

if(x == 1)
{
System.out.println(“716550366”);
continue;
}
int z = N.intValue();
if(z==0)
{
System.out.println(“0”);
continue;
}

`````` factor(N);

int sz = v.size();
Collections.sort(v);
long cnt = 0;
long tot = 1;
for(int i=0;i<sz;i++){

cnt = 0;
while(i+1<sz&&v.get(i).equals(v.get(i+1))){

cnt++; i++;
}
cnt++;
tot *= (cnt+1);
}

long temp = N.longValue();
System.out.println(power(temp,tot/2,1000000007) % 1000000007);
``````

}
}
}
//code give NZEC
//applied pollard rho for the prime factroization

I also tried Pollard-Rho algorithm for prime factorization in Java. I used this implementation:
http://introcs.cs.princeton.edu/java/99crypto/PollardRho.java.html