0%

牛客 16499 解方程 (数学、Python)

链接:https://ac.nowcoder.com/acm/problem/16499
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld

题目描述

已知多项式方程:
a0+a1x+a2x^2^+…+anx^n^=0
求这个方程在[1, m]内的整数解(n和m均为正整数)。

输入描述:

第一行包含2个整数n、m,每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数,依次为a0,a1,a2,……,an。

输出描述:

第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。

枚举1~m中的所有整数,代入多项式,判断值是否为0

求一元n次多项式可以用到秦九韶算法
在这里插入图片描述
但还是会超时,只能得70分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n, m = list(map(int, input().split()))
a = []
mod = 1000000007
for i in range (n+1):
a.append(int(input())%mod)

res = []
for i in range (1, m+1):
ans = a[n]
for j in range (n-1,-1,-1):
ans = (ans*i + a[j])%mod
if ans == 0:
res.append(i)
print(len(res))
res.sort()
for i in res:
print(i)
-------------    本文结束  感谢您的阅读    -------------