ACM数论----秦九昭算法

一.算法简介

一般地，一元n次多项式的求值需要经过(n+1)*n/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。在人工计算时，一次大大简化了运算过程。

ACM数论----秦九昭算法

二.算法应用

1.大整数取模（hdu 1212 Big Number）

（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 + 7;
char str[maxn];
int Horner(int mod){//秦九昭算法
    int len = strlen(str);
    int ans = 0;
    for(int i = 0;i<len;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("%d\n",num);
    }
    return 0;
}

2.UVA10929

代码：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000 + 7;
char str[maxn];
int Horner(){
   int len = strlen(str);
   int ans = 0;
   for(int i = 0;i<len;i++){
      ans = (ans*10 + str[i] - '0')%11;
   }
   return ans;
}
int main()
{
    while(scanf("%s",str)!=EOF){
        if(str[0]=='0'&&strlen(str)==1)break;
        int num = Horner();
        if(num)printf("%s is not a multiple of 11.\n",str);
        else printf("%s is a multiple of 11.\n",str);
    }
    return 0;
}

ACM数论----秦九昭算法

相关推荐