C语言中大数相乘求和的模运算是怎样的

这篇文章主要为大家分析了C语言中大数相乘求和的模运算是怎样的的相关知识点，内容详细易懂，操作细节合理，具有一定参考价值。如果感兴趣的话，不妨跟着跟随小编一起来看看，下面跟着小编一起深入学习“C语言中大数相乘求和的模运算是怎样的”的知识吧。

题目如上图，这是在程序设计或者ACM中常见的数学题目，结合前人经验总结了一下。（开发语言c）

#include<stdio.h>

#define INT64 __int64

INT64 PowerMode(INT64 basenum, INT64 powernum, INT64 modenum){

//计算basenum^powernum % modenum

//a^(2c) = (a^c)^2；

    //a^(2c+1) = a*((a^c)^2)；

    //比如a=3,b=13时，我们把b写成二进制的形式13(10)=1101(2)

//我们从低位到高位运算，每运算一位可以将b右移一位，上面的例子可以转化成3^13 = 3^1 * 3^4 * 3^8

//(a*b)%p = a%p * b%p %p

//(a^b)%p = (a%p)^b

//a^13%m=(a^8*a^4*a^1)%m=a^8%m * a^4%m * a^1%m %m

INT64 result = 1;

while(powernum){

if(powernum&1)

result = result * basenum % modenum;

basenum = basenum * basenum % modenum;

powernum>>=1;

}

return result;

}

INT64 MultiAdd(INT64 countnum, INT64 basenum, INT64 modenum){

//(a+b)%p = (a%p + b%p) %p

    //

INT64 sum = 0;

for(int i=0; i<=countnum; i++){

sum += (countnum-i)%modenum * PowerMode(basenum,i,modenum) %modenum;

sum %= modenum;

}

return sum;

}

int main(){

INT64 testnum;

scanf("%I64d",&testnum);

while(testnum--){

INT64 n,m,x;

scanf("%I64d %I64d %I64d",&n,&m,&x);

INT64 value = MultiAdd(n,x,m);

        printf("%I64d\n",value);

}

return 0;

}

关于“C语言中大数相乘求和的模运算是怎样的”就介绍到这了,更多相关内容可以搜索亿速云以前的文章，希望能够帮助大家答疑解惑，请多多支持亿速云网站！