3067448_wa.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;
import java.math.*;

public class Main 
{
    static int num[] = new int [10001];
    static int cnt[] = new int [10001];
    static BigInteger mod = new BigInteger("9901");
    public static void main(String[] args) 
    {
        Scanner cin = new Scanner (System.in);
        int a, b, m, t, i, j;
        
        a = cin.nextInt();
        b = cin.nextInt();
        m = 0;
        if(a%2==0)
        {
            num[m] = 2;
            while(a%2==0)
            {
                a /= 2;
                cnt[m]++;
            }
            cnt[m] *= b;
            m++;
        }
        t = (int)Math.sqrt((double)(a))+1;
        for(i = 3; i < t&&a!=1; i+=2)
        {
            if(a%i==0)
            {
                num[m] = i;
                while(a%i==0)
                {
                    a /= i;
                    cnt[m]++;
                }
                cnt[m] *= b;
                t = (int)Math.sqrt((double)(a))+1;
                m++;
            }
        }
        if(a!=1)
        {
            num[m] = a;
            cnt[m] = b;
            m++;
        }
        int ans = 1;
        for(i = 0; i < m; i++)
        {
            int tmp = (power(BigInteger.valueOf(num[i]),cnt[i]+1).intValue()+9900)%9901;
            for(j = 1; j < 9901; j++)
            {
                if((j*((num[i]-1)%9901))%9901==1)
                    break;
            }
            tmp *= j;
            ans *= tmp;
            ans %= 9901;
        }
        System.out.println(ans);
    }

    private static BigInteger power(BigInteger p, int n)
    {
        if(n==1)
        {
            return p.mod(mod);
        }
        if(n%2==1)
        {
            return p.multiply(power(p,n-1)).mod(mod);
        }
        return power(p.multiply(p).mod(mod),n/2).mod(mod);
    }
}