C++快速幂与大数取模算法示例
发布时间:2020-12-16 05:18:41 所属栏目:百科 来源:网络整理
导读:一、快速幂 其实就是求 (a^b)% p ,(其中a,b,p都比较大在int范围内)这类问题。 首先要知道取余的公式: (a*b)%p=(a%p*b%p)%p 。 那么幂不就是乘机的累积吗,由此给出代码: int fast(int a,int b,int p){ long long a1=a,t=1; while(b0) { if(b a1=(a
一、快速幂 其实就是求 首先要知道取余的公式: 那么幂不就是乘机的累积吗,由此给出代码: int fast(int a,int b,int p) { long long a1=a,t=1; while(b>0) { if(b&1) /如果幂b是奇数多乘一次,因为后边会除2变偶数,(7/2=3) t=(t%p)*(a1%p)%p; a1=(a1%p)*(a1%p)%p; b/=2; } return (int)(t%p); } 二、大数取模 它的原理就是这个取余公式: 那么大数可以看做每一位的那位数字乘以自身的权然后每位相加。 如:12345678=(1*10000000)+(2*1000000)+…+8。 代码如下: char s[200]; #define mod 10000010; int main() { while(gets(s)) { int k=strlen(s),sum=0; for(int i=0;i<k;i++) sum=(sum*10+s[i]-'0')%mod; /当然要是担心sum还可能溢出,那就对里边再拆开来取余 cout<<sum<<endl; } } 三、总结 以上就是本文的全部内容,希望对大家的学习和工作能有所帮助。如果有疑问可以留言交流。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |