C++疾速冪與年夜數取模算法示例

C++疾速冪與年夜數取模算法示例。本站提示廣大學習愛好者：（C++疾速冪與年夜數取模算法示例）文章只能為提供參考，不一定能成為您想要的結果。以下是C++疾速冪與年夜數取模算法示例正文

1、疾速冪

其實就是求（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);

}

2、年夜數取模

它的道理就是這個取余公式： （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;

} }

3、總結

以上就是本文的全體內容，願望對年夜家的進修和任務能有所贊助。假如有疑問可以留言交換。