大数取余
发布时间:2020-12-14 02:46:07 所属栏目:大数据 来源:网络整理
导读:整理一下自己遇到的两种大数取余类型的题目,如果遇到其他类型以后还会接着去补充。 一、A^B mod m 几个基本公式: A m,且B是一个较大的数,A^B非常巨大,先求A^B再用m取模是不现实的。利用上面公式,我们可以进行如下代换: 算法: //计算 exp =a^n mod m /
整理一下自己遇到的两种大数取余类型的题目,如果遇到其他类型以后还会接着去补充。 A < m,且B是一个较大的数,A^B非常巨大,先求A^B再用m取模是不现实的。利用上面公式,我们可以进行如下代换: 算法: //计算exp=a^n mod m
//输入:a,n,m
//输出:exp
int exp_mod(int a,int n,int m)
{
int exp,A; //exp表示a^n,A是A_i
exp=1;
A=a%m;
while(n>0)
{
if(n%2 != 0)
exp=(exp*A)%m;
A=(A*A)%m;
n=n/2;
}
return exp;
}
二、A%B
算法: int MOD(string a,int mod)
{
int len=a.length();
int t=0;
for( int i = 0; i < len; i++ )
{
t*=10;
t+=a[i]-'0';
if( t >= mod )
t=t%mod;
}
return t;
}
参考博客:http://www.cnblogs.com/lsx54321/archive/2012/07/25/2607602.html (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |