nyoj 102 同余幂算法

灰太狼 2022-03-20 13:58 179阅读 0赞

## 次方求模 ##

时间限制： 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

来源

[\[张云聪\]原创][Link 1]

/\*需要快速的求出同余幂bn mod m，  
其中b，n，m都是比较大的整数。例如取b=12345678，n=456789，  
直接计算显然是不可行的，可以把n按二进制展开，则n=456789就  
变成了1101111100001010101，这样每次只需要求b mod m，b2 mod m，  
... b2^(k-1) mod m，然后把对应位置上的二进制是1的项乘起来，  
每次乘完后求除m的余数即可，大大降低了计算的复杂度,当然这里要在程序中的话可以  
通过处理就通过对b取余2，关于这些处理可以自己想办法、  
在《离散数学及其应用》里介绍了这种方法，用于密码学中。\*/

#include <iostream>
    
    using namespace std;
    
    long long powermod(long long a , long long b , long long c );
    
    int main()
    {
        int n ;
        long long a , b , c ;
        long result = 0 ;
        cin>>n;
        while ( n-- )
        {
            cin>>a>>b>>c;
            result = powermod(a,b,c);
            cout<<result<<endl;
        }
        return 0;
    }
    long long powermod(long long a , long long b , long long c )
    {
        long long t = 1 ;
        if ( b == 0 )
        {
            return 1%c;
        }
        if ( b == 1 )
        {
            return a%c;
        }
        t = powermod(a,b/2,c);
        t = t*t%c;
        if ( b%2 == 1 )
        {
            t = t*a%c ;
        }
        return t;
    
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%5B%E5%BC%A0%E4%BA%91%E8%81%AA%5D%E5%8E%9F%E5%88%9B