大数取模

发布时间：2020-12-14 02:55:21 所属栏目：大数据来源：网络整理

导读：a+b)%n=(a%n+b%n)%n (a-b)%n=(a%n-b%n+n)%n 为什么要加n，由于a%n可能小于b%n,所以加n保证为正整数 a*b%n=(a%n*b%n)%n 这些事大整数取模的基础 int mod(char str[],int num) { ? ? ?? int number[100]; ? ? ?? for(int i=0;istrlen(str);i++) ? ? ?? ?number

a+b)%n=(a%n+b%n)%n

(a-b)%n=(a%n-b%n+n)%n

为什么要加n，由于a%n可能小于b%n,所以加n保证为正整数

a*b%n=(a%n*b%n)%n

这些事大整数取模的基础

int mod(char str[],int num)

{

? ? ?? int number[100];

? ? ?? for(int i=0;i<strlen(str);i++)

? ? ?? ?number[i]=str[i]-'0';

? ? ?? int remainder=0;

? ? ?? {

? ? ?? ?? ?? remainder=((long long)remainder*10+number[i])%num;

? ? ?? }

? ? ?? return remainder;

}

之所以强制转换为long long ，是为了防止乘法过程中溢出

幂取模

int pow_mod(int a,int n,int m)

? ? ?? if(n==1) return a;

? ? ?? else?

? ? ?? ?? ?? int x=pow_mod(int a,int n/2,int m)

? ? ?? ?? ?? long long x=(long long)x*x%m;

? ? ?? ?? ?? if(n%2==1) x=(long long)x*a%m;

? ? ?? ?? ?? return (int)x;

? ? ?? ?}

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!