【数论系列】秦九昭算法

编程基础 • 2024-12-25 16:06 • 阅读 6

一. 算法介绍

二. 算法应用

1. HDU1212 Big Number

2. UVA10929

一. 算法介绍

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

二. 算法应用

1. HDU1212 Big Number

Problem Description

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

大整数取模。由秦九昭算法可知，任意一个整数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个多项式每步取模。

#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; }

今天的文章【数论系列】秦九昭算法分享到此就结束了，感谢您的阅读。

【数论系列】 秦九昭算法

一. 算法介绍

二. 算法应用

1. HDU1212 Big Number

2. UVA10929

相关推荐

【数论系列】秦九昭算法