本來是想要用遞迴寫 

但因為最近剛好有看到DP的作法所以想要試試看

但是卻TLE了= =

試了題目給定的測資和自己出了幾個測資測試

發覺實在是找不到有什麼地方可能造成TLE的

所以想要請教板上的強者們.

以下是我的code.

#include <stdio.h>

int main( void )
{
    int b, p, m;
    int a[50000];
    a[0] = 1;

    while( scanf( "%d%d%d", &b, &p, &m ) != EOF )
    {
          if( b > m )
          b = b % m;

          if( m == 1 || b == 0 )
          printf( "0\n" );

          else if( b == 1 || p == 0 )
          printf( "1\0" );

          else
          {
               a[1] = b;

               int i = 2, j;
               while( 1 )
               {
                a[i] = ( a[i-1] * b ) % m;

                for( j = 1; j < i; j++ )
                {
                     if( a[j] == a[i] )
                     break;
                 }

                if( j != i )
                break;

                else
                i++;
              }

               printf( "%d\n", a[ (p-j)%(i-j) + j ] );
          }
     }

return 0;
}

可以用2進位法

也就是說原本2的5次方

5換成2進位是

101

2的5次方就變成

2^1*1+2^2*0+2^4*1

在下的解法參考一下

你的作法只是要找餘數的循環對吧

基本上找餘數的循環也是可以  不過每次跑i的話  會很慢

用int Flag[50000];  //在裡面把餘數那格標上長度

假設長度是L 餘數是M好了

那就Flag[M]=L  假設跑到Flag[M]發現此格出現過   代表循環了

加速的次方

#include\ \
using namespace std;
int main()
{
    int a,b;   
    while(scanf("%d%d",&a,&b)==2)
    {
    int ans=1;
    while(b!=0)
    {
    if(b%2)
    ans*=a;
    a*=a;
    b/=2;
    }
    printf("%d\n",ans);
    }
}