首页 > 代码库 > poj---1995---整数幂取模

poj---1995---整数幂取模

先上题目 ~

    touch me

以前只做过 矩阵快速幂取模~

这题是 整数幂取模  差不多

一开始 忘记 拆分成二进制 进行离散了  果断TLE ,...

 

这边用到的 * + % 这3个运算符 混合运算时 还是很容易搞混的

 

 1 #include <iostream> 2 using namespace std; 3  4 __int64 mod , sum; 5 void solve( int x , int n ) 6 { 7     __int64 result = 1; 8     while( n ) 9     {10         if( n&1 )11         {12                result = ( result * x )%mod;13         }14         x = ( (x%mod) * (x%mod) )%mod;15            n >>= 1;16     }17     sum = ( sum + result ) % mod;18 }19 20 int main()21 {22     int t , n;23     __int64 x , y;24     while( cin>>t )25     {26         while( t-- )27         {28             sum = 0;29             scanf( "%I64d",&mod );30             scanf( "%d",&n );31             for( int i = 0 ; i<n ; i++ )32             {33                 scanf( "%I64d %I64d",&x,&y );34                 solve( x , y );35             }36             printf( "%I64d\n",sum );37         }38     }39     return 0;40 }
View Code