【分治】取余运算-白红宇

【分治】取余运算

阅读量：5163 次

发布时间：2019-06-13

本文共 942 字，大约阅读时间需要 3 分钟。

问题 E: 【分治】取余运算

时间限制: 1 Sec 内存限制: 128 MB

提交: 16 解决: 6

[][][]

题目描述

输入b，p，k的值，求b

^p mod k的值。其中b，p，k*k为长整型数。

输入

三个整数，分别为b，p，k的值

输出

^p mod k

样例输入

2 10 9

样例输出

2^10 mod 9=7

提示

解题思路：分治，顾名思义，把一个大问题分解为多个小问题。

　　　这里有一个公式，利用这个公式通过递归求得。

代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std; //a*b % n = (a % n)*(b % n) % nlong int mod_fenzhi(long int b,long int p,long int k){    if(p==1){        return b%k;    }    if(p==2){        return b*b%k;    }    if(p%2==0){        long int aa=mod_fenzhi(b,p/2,k);        return aa*aa%k;    }    if(p%2==1){        long int aa=mod_fenzhi(b,p/2,k);        return aa*aa*b%k;    }}int main(){    long int b;    long int p;    long int k;    long int jieguo;    while(scanf("%ld %ld %ld",&b,&p,&k)!=EOF){        jieguo=mod_fenzhi(b,p,k);        printf("%ld^%ld mod %ld=%ld\n",b,p,k,jieguo);    }    return 0;}