P2312 解方程

P2312 解方程

我借鉴了一下某位不愿透露姓名的丁大佬的代码,他讲了一遍。。。但是我并没有听懂

这个题目呢我们用到了秦九韶算法

把一个n次多项式
 
 
改写成如下形式:
 
 
 
 
 
 
求多项式的值时,首先计算最内层括号内一次多项式的值,即
 
 
 
然后由内向外逐层计算一次多项式的值,即
 
 
 
 
 
这样,求n次多项式f(x)的值就转化为求n个一次多项式的值。
 
结论:对于一个n次多项式,至多做n次乘法和n次加法。

代码:

#include <cstdio>
const long long Mod = (int)1e9 + 7;
const int maxN = 100 + 5;
const int maxM = (int)1e6 + 5;

int N, M;
int arr[maxN];

void Fscan(int &tmpX) 
{
int Ch = getchar(), F = ' '; long long tmp = 0; while (Ch < '0' || Ch > '9')
{ F
= Ch; Ch = getchar(); } while ('0' <= Ch && Ch <= '9')
{ tmp
= ((tmp << 3) + (tmp << 1) + Ch - '0') % Mod; Ch = getchar(); } tmpX = (int)(F == '-' ? -tmp : tmp); } void Read()
{ scanf(
"%d%d", &N, &M); for (int i = 0; i <= N; ++i) Fscan(arr[i]); } int T, Que[maxM]; long long Calc(const int &X)
{
long long Ans = 0; for (int i = N; i; --i) Ans = ((Ans + (long long)arr[i]) * (long long)X) % Mod; Ans = (Ans + (long long)arr[0]) % Mod; return Ans; } void Solve()
{
for (int i = 1; i <= M; ++i) if (!Calc(i)) Que[++T] = i; } int main() { Read(); Solve(); printf("%d ", T); for (int i = 1; i <= T; ++i) printf("%d ", Que[i]); return 0; }
原文地址:https://www.cnblogs.com/xiaoyezi-wink/p/10667034.html