NYOJ127 星际之门（一）(最小生成数的个数+快速幂) - c++编程基础

可以证明，修建N-1条虫洞就可以把这N个星系连结起来。

现在，问题来了，皇帝想知道有多少种修建方案可以把这N个星系用N-1条虫洞连结起来？

输入第一行输入一个整数T,表示测试数据的组数(T<=100)
每组测试数据只有一行，该行只有一个整数N，表示有N个星系。(2<=N<=1000000)
输出对于每组测试数据输出一个整数，表示满足题意的修建的方案的个数。输出结果可能很大，请输出修建方案数对10003取余之后的结果。样例输入

2
3
4

样例输出

3
16

题目分析：

快速幂+完全图的最小生成树的个数，n个顶点的最小生成树的个数为n^(n-2)。

AC代码1 O(n)：

 
/**
 *在一个n阶完全图的所有生成树的数量为n的n-2次方
 */
#include
      
       
#include
       
         #include
         #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                  
                    #define MOD 10003 using namespace std; int Sum(int n){ int res=n; for(int i=1;i<=n-3;i++){ res*=n; res%=MOD; } return res; } int main() { int n,t; cin>>t; while(t--){ cin>>n; if(n==2){//只有一中 cout<<1<
                   
                    AC代码2 O(logn)
                    ?
                    ?
                     
/**
 *在一个n阶完全图的所有生成树的数量为n的n-2次方
 */
#include
                     
                      
#include
                      
                        #include
                        #include
                        
                          #include
                         
                           #include
                          
                            #include
                           
                             #include
                            
                              #include
                             
                               #include
                              
                                #include
                               
                                 #include
                                
                                  #include
                                 
                                   #define MOD 10003 using namespace std; int Mod(int a,int b)//快速幂 { int ret=1; int tmp=a; while(b) { //奇数存在 if(b&1) ret=ret*tmp%MOD; tmp=tmp*tmp%MOD; b>>=1; } return ret; } int main() { int n,t; cin>>t; while(t--){ cin>>n; if(n==2){//只有一中 cout<<1<
                                  
                                   ?
                                   
                                    
                                     
                                      
                                       ?