526互联

秦九韶算法学习笔记

发布时间 2024-01-13 10:20:05作者: Light_starup

快速求多项式 —— 秦九韶算法

计算 \(\sum^n_i{a_i \times x^i}\) 的值。

1. 朴素算法

算出每一项的值再相加，总共要进行 \(\frac{n(n + 1)}{2}\) 次乘法，\(n\) 次加法。

2. 秦九韶算法

\(a_0 + a_1x + a_2x^2 + \dots a_n x^n = (((a_nx + a_{n - 1})x + a_{n - 2}\dots)x + a_1)x + a_0\) 可以只进行 \(n\) 次乘法，\(n\) 次加法，大大降低了时间复杂度。

例题

题目描述

已知多项式方程：

\[a_0+a_1x+a_2x^2+\cdots+a_nx^n=0 \]

求这个方程在 \([1,m]\) 内的整数解（\(n\) 和 \(m\) 均为正整数）。
对于 \(100\%\) 的数据：\(0<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^6\) 。

对于这道题我们可以利用秦九韶算法求解，枚举 \([1, m]\) 的每一个数，然后将其带入多项式求值，最终如果结果为 \(0\)，就记录答案。


#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll Mod = 1e9 + 7;

inline ll read(){
  	ll f = 1,x = 0;
  	char ch = getchar();
  	while(!isdigit(ch)){
		if(ch == '-')f = -1;
  		ch = getchar();
  	}
  	while(isdigit(ch)){
  		x = (x << 1) + (x << 3) + (ch ^ 48);
  		x %= Mod;
  		ch = getchar();
  	}
  	return x * f;
}
inline void print(int x){
  	if(x > 9)print(x / 10);
  	putchar(x % 10 + '0');
}

ll a[101];
int n, m;

bool check(ll x){
	ll sum = 0;
	for(ll i = n; i >= 1; i--)
		sum = ((a[i] + sum) % Mod * x) % Mod;
	sum = (sum + a[0]) % Mod;
	return !(sum);
}

ll ans[1000010], tot = 0;

signed main(){	
	cin >> n >> m;
	for(int i = 0; i <= n; i++){
		a[i] = read();
	}
	for(ll i = 1; i <= m; i++){
		if(check(i))ans[++tot] = i;
	}
	cout << tot << endl;
	for(int i = 1; i <= tot; i++){
		cout << ans[i] << endl;
	}
  	return 0;
}