首页 > 代码库 > 取余运算（mod）（分治）
取余运算（mod）（分治）
【问题描述】
输入b，p，k的值，求bp mod k的值。其中b，p，k*k为长整形数。
【输入样例】mod.in
2 10 9
【输出样例】mod.out
2^10 mod 9=7
题目的只要特点是数据过大，
下面先介绍一个原理：A*B%K = (A%K )*(B% K )%K。显然有了这个原理，就可以把较大的幂分解成较小的；
因为是2的10次方数据过大，那有什么办法可以把数据给拆开呢？2的10次方，为两个2的5次方的乘积，而2的5次方又可以
分解为两个2的2次方和一个2的一次方的乘积，利用上述的原理，我们只需要把拆开的数进行模运算就可以，这与大数进行模运算方法相同，
而且拆开的每个数模运算完成之后就可以计算出大数的结果，所以算法是分治。
【代码】
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int b,p,k; int f(int); int main() { scanf("%d%d%d",&b,&p,&k); b%=k;//防止b过大 cout<<f(p); return 0; } int f(int x) { if(x==0)return 1;//任何数的0次方模k都等于1 int tmp=f(x/2)%k;//a*b%k=a%k*b%k%k; tmp=(tmp*tmp)%k; if(x%2==1)tmp=(tmp*b)%k; return tmp; }
取余运算（mod）（分治）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。