首页 > 代码库 > ACM 取模
ACM 取模
取模公式：
(a+b) mod n=((a mod n)+(b mod n))%n
(a-b) mod n=(a mod n -b mod n +n)mod n
a*b mod n =(a mod n)*(b mod n)mod n
1大整数取模：输入n，m求n%m，其中n<=10^1000000,m<=10^9
?
|
1
2
3
4
5
6
7
8
|
//大整数取模 int big_number_mod(char *str, int m){ int len = strlen(str), res = 0; for (int i = 0; i < len; i++){ res = (res * 10 + str[i] - ‘0‘) % m; } return res; } |
2.幂取模 an mod m的值,a,n,m<=10^9。采用分治算法可以在O(longn)算出来,例如a29=(a14)2a，而a14=(a7)2,a7=(a3)2a,a3=a2a。
?
|
1
2
3
4
5
6
7
8
|
//幂取模:计算a^n mod m //O(longn) int pow_mod(int a, int n, int m){ if (n == 0)return 1; int x = pow_mod(a, n / 2, m); LL ans = (LL)x*x %m; if (n & 1)ans = ans*a%m; return (int)ans; |
3.快速幂取模运算：计算an mod m 。采用快速幂将n分解为二进制。例如n=11，则10=10112,于是a11=a1+2+8,可以依次计算a,a2,a4,a8,然后计算出a11
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
//快速幂取模:计算a^n mod m //O(longn) int quick_pow_mod(int a, int n, int m){ if (n == 0)return 1; int res = 1; while (n > 0){ if (n & 1) res=res*a%m; a = (a%m)*(a%m)%m; //防止溢出 n >>= 1; } return res; } |
ACM 取模
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。