big^n.cpp

大数的模运算。 a^b ％ m a可以为1000位的大数

/*
soj3151
x=a*10+b
x%m=((a%m)*10+b)%m 
a*b mod c = ((a mod c)*b mod c
*/
#include <stdio.h>
#include <string.h>
char     str[10011];
int      t  , m , ans , n;
long     long     calc(long long b , long long e , long long m)
{
               long long a=1;
               if(b==0||m==1){return 0;}
               if(e==0){return 1;}
               while(e)
               {
                   if( e & 1)  a  =  ( a * b)  %  m;    // mod2  = 1
                   b = ( (b % m)*(b % m)) % m; 
                   e /= 2;
               }
              return a;
         
}
int     main()
{
         freopen("input2.txt","r",stdin);
         freopen("output2.txt","w",stdout);
         scanf("%lld\n",&t);
         long long Len , i;
         while(t)
         {
                 -- t ; ans = 0;
                 scanf("%s%lld%lld\n",&str,&n,&m); 
                 Len = strlen(str);
                 for(i = 0 ; i < Len ; i++)
                 ans = (ans*10 + str[i] - 48 ) % m;
                 printf("%lld\n",calc(ans , n , m));      
         }
}