GDUFE-OJ 1203x的y次方的最后三位数 快速幂

时间：2021-03-05 19:30:46

嘿嘿今天学了快速幂也~~

Problem Description:

   求x的y次方的最后三位数 。

Input:

一个两位数x和一个两位数y。

Output:

输出x的y次方的后三位数。

Sample Input:

13 13

Sample Output:

253
思路：快速幂求a^b，然后mod c。因为是随便输入的a，b，所以范围很大，而题目只需求最后三位，所以百位以上的计算不用理了，直接%1000。
 #include <stdio.h>
 int main()
 {
     unsigned long long a,b;
     while(scanf("%llu%llu",&a,&b)!=EOF)
     {
         unsigned ,d=a;
         )
         {
         !=)//如果是0则无需计算，因为n*1=n
             c*=d%;
             d*=d%;
             b>>=;
         }
         >)
         printf();
         >)
         printf();
         else
         printf();
     }
     ;
 }

Tip：以上mod c是因为怕数字过大爆了，一是因为a的b次mod c，二是因为早晚要mod c，所以早mod 无所谓。

小知识：

快速幂原理：a^b,将b拆成二进制数相加的形式，从而使运算次数减少

Example：a^11=a^(2^0+2^1+2^3)，时间复杂度为O（log11）。

 scanf("%d%d",&a,&b)
         ,d=a;
         )
         {
         !=)//取b的二进制数的最后一位（相当于b%2!=0）
             c*=d;
             d*=d;  //每往右推一位，d倍增，2^0 2^1 2^2……
             b>>=;//将b的二进制数往右推一位（相当于b/=2）
         }
 printf("%d\n",c);//c=a^b

相关文章