CF 334 div.2-D Moodular Arithmetic

思路：

易知k = 0的时候答案是p^p-1，k = 1的时候答案是p^p。

当k >= 2的时候，f(0) = 0，对于 1 <= n <= p - 1，如果f(n)确定，由题意可知f(kⁱn mod p)也随之确定，那么这种迭代什么时候停止呢？这就需要找出循环节，即能使k^m mod p = 1的最小的m，这个m就是k的阶数o(k)。这里(G = N_p - {0}, 模p乘法)实际上是一个循环群，设G中的元素k的阶数o(k) = m, 则k作为生成元生成的子群也是循环群，并且子群的阶为m且m能整除群的阶p-1。（参见离散数学（邓米克，邵学才等编著）清华大学出版社，p252）)，所以剩下的p-1(1 ~ p-1)个数实际上构成了(p - 1) / m 个同构的子循环群。这种情况下，答案就是

p^{(p - 1)/m}。

实现：

import java.util.*;

public class Main {

    private static final int mod = 1000000007;
    public static long pow(long x, long n, long mod) {
        long res = 1;
        while (n > 0) {
            if((n & 1) == 1)
                res = res * x % mod;
            x = x * x % mod;
            n >>= 1; 
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long p = in.nextInt(), k = in.nextInt();
        if (k == 0)
            System.out.println(pow(p, p - 1, mod));
        else if (k == 1)
            System.out.println(pow(p, p, mod));
        else {
            long ord = 1;
            long tmp = k;
            while (tmp != 1) {
                tmp = tmp * k % p % mod;
                ord++;
            }
            System.out.println(pow(p, (p - 1) / ord, mod));
        }    
    }
}