快速幂+大数取模

2018-06-17 23:50:52来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

快速幂+大数取模

 

快速幂,其实就是求(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(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);

}

顺便把大数取模也给出吧,它的原理就是这个取余公式:(a+b)%p=(a%p+b%p)%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;

} }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:并查集

下一篇:观光浏览