整数快速幂——次方求模

迷南。 2022-06-12 01:36 225阅读 0赞

先上代码：

unsigned Power(unsigned n, unsigned p)  
\{ // 计算n的p次方  
    unsigned odd = 1; //oddk用来计算“剩下的”乘积  
    while (p > 1)  
    \{ // 一直计算到指数小于或等于1  
       if (( p & 1 )!=0)  
      \{ // 判断p是否奇数，偶数的最低位必为0  
             odd \*= n; // 若odd为奇数，则把“剩下的”乘起来  
      \}  
      n \*= n; // 主体乘方  
      p /= 2; // 指数除以2//或p=p>>1;  
     \}  
    return n \* odd; // 最后把主体和“剩下的”乘起来作为结果  
\}

## 快速求幂算法。 ##

快速求正整数次幂，当然不能直接死乘。举个例子：  
   
3 ^ 999 = 3 \* 3 \* 3 \* … \* 3  
   
直接乘要做998次乘法。但事实上可以这样做，先求出2^k次幂：  
   
3 ^ 2 = 3 \* 3  
3 ^ 4 = (3 ^ 2) \* (3 ^ 2)  
3 ^ 8 = (3 ^ 4) \* (3 ^ 4)  
3 ^ 16 = (3 ^ 8) \* (3 ^ 8)  
3 ^ 32 = (3 ^ 16) \* (3 ^ 16)  
3 ^ 64 = (3 ^ 32) \* (3 ^ 32)  
3 ^ 128 = (3 ^ 64) \* (3 ^ 64)  
3 ^ 256 = (3 ^ 128) \* (3 ^ 128)  
3 ^ 512 = (3 ^ 256) \* (3 ^ 256)  
   
再相乘：  
   
3 ^ 999  
= 3 ^ (512 + 256 + 128 + 64 + 32 + 4 + 2 + 1)  
= (3 ^ 512) \* (3 ^ 256) \* (3 ^ 128) \* (3 ^ 64) \* (3 ^ 32) \* (3 ^ 4) \* (3 ^ 2) \* 3  
   
这样只要做16次乘法

例题：nyoj——次方求模[点击打开链接][Link 1]

## 次方求模 ##

时间限制：1000 ms  |  内存限制：65535 KB

难度：3

## 描述 ##

求a的b次方对c取余的值

## 输入 ##

第一行输入一个整数n表示测试数据的组数（n<100）  
每组测试只有一行，其中有三个正整数a,b,c(1=<a,b,c<=1000000000)

## 输出 ##

输出a的b次方对c取余之后的结果

## 样例输入 ##

3
    2 3 5
    3 100 10
    11 12345 12345

## 样例输出 ##

3
    1
    10481

#include<bits/stdc++.h>
    using namespace std;
    int Power(long long int n, long long int p,long long int c)
    {
        long long int odd=1;
        while (p>1)
        {
           if(p&1)
          {
                odd=(odd%c)*(n%c)%c;
          }
          n=(n%c)*(n%c)%c;
          p=p>>1;
         }
        return n*odd%c;
    }
    int main()
    {
        int t;
        long long int a,b,c;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld %lld %lld",&a,&b,&c);
            cout<<Power(a,b,c)<<endl;
        }
        return 0;
    }

当a特别大的时候，就要用公式，x\*x%c=(x%c)\*(x%c)%c

[Link 1]: http://acm.nyist.net/JudgeOnline/problem.php?pid=102