【NYOJ】127.星际之门（一）

 1 /*
 2 在一个n阶完全图的所有生成树的数量为n的n-2次方
 3 所以这道题就是求n^(n-2) mod 10003 
 4 证明：http://blog.himdd.com/?p=979 （不懂） 
 5 */
 6 
 7 #include <iostream>
 8 using namespace std;
 9 
10 int main()
11 {
12     int m;
13     
14     cin >> m;
15     
16     while (m--)
17     {
18         long long n;
19         
20         cin >> n;
21         
22         long long ans = 1, p = n-2;
23         
24         while (p)                    //二分求幂  求n^m 
25         {
26             if (p%2)
27                 ans = ans*n%10003;
28             
29             n = n*n%10003;
30             
31             p /= 2;
32         }
33         
34         cout << ans << endl;
35     }
36 }