【分治】快速模幂

问题 R: 【分治】快速模幂

时间限制: 1 Sec  内存限制: 64 MB
提交: 8  解决: 7
[提交][状态][讨论版]

题目描述

试求a^b%n的值，其中a、b、n均为整数范围内的数。

输入

三个整数a、b和n

输出

a^b%n的值

样例输入

1 1 1

样例输出

0
解题思路：快速模幂比快速幂多了取余，和另一个快速取余是一样的。有公式。
代码：

#include <iostream>
#include <cstdio>

using namespace std;

//a*b % n = (a % n)*(b % n) % n
long long int mo(long long int x,long long int n,long long int a){
    if(x==a){
        return 0;
    }
    if(n==1){
        return x%a;
    }
    if(n==2){
        return x*x%a;
    }
    if(n==3){
        return x*x*x%a;
    }
    if(n==4){
        return x*x*x*x%a;
    }
    if(n%2==0){
        return mo(x,n/2,a)*mo(x,n/2,a)%a;
    }
    if(n%2!=0){
        return mo(x,(n-1)/2,a)*mo(x,(n-1)/2,a)*x%a;
    }
}

int main()
{
    int x;
    int n;
    int a;
    long long int jieguo;
    while(scanf("%d %d %d",&x,&n,&a)!=EOF){
        jieguo=mo(x,n,a);
        printf("%lld
",jieguo);
    }
    return 0;
}