python | 秦九昭算法详细介绍

help(reduce)结果是

Help on built-in function reduce in module _functools:
reduce(...)
 reduce(function, sequence[, initial]) - value
 Apply a function of two arguments cumulatively to the items of a sequence,
 from left to right, so as to reduce the sequence to a single value.
 For example, reduce(lambda x, y: x y, [1, 2, 3, 4, 5]) calculates
 ((((1 2) 3) 4) 5). If initial is present, it is placed before the items
 of the sequence in the calculation, and serves as a default when the
 sequence is empty.

中文解释下 就是操作一个集合 把一系列数迭代操作成一个数。

不理解就看蓝色字的例子

1 题意

给你一个长度不超过1000的大数A 还有一个数值不超过100000的B 快速求A % B。

2 分析

由秦九昭算法可知 任意一个整数n akak-1ak-2.......a2a1a0可以拆分为

n (((((ak)*10 ak-1)*10 ak-2)*10 .......)*10 a1)*10 a0

例如 1234 ((1*10 2)*10 3)*10 4

 则大整数取模就可以转化为n个多项式每步取模。

3 贴份代码

#include iostream 
#include bits/stdc .h 
using namespace std;
const int maxn 10000 
char str[maxn];
int Horner(int mod){//秦九昭算法
 int len strlen(str);
 int ans 
 for(int i i i ){
 ans (ans*10 str[i] - 0 )%mod;
 return ans;
int main()
 int mod;
 while(scanf( %s%d ,str, mod)! EOF){
 int num Horner(mod);
 printf( %dn ,num);
 return 0;
}