洛谷查看此题
https://www.luogu.com.cn/problem/P2312
我们发现这个方程具有公因数x
于是对于原方程有
=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x^1+a_0
=\left( a_nx^{n-1}+a_{n-1}x^{n-2}+\cdots +a_2x+a_1 \right) x+a_0
=\left( \left( a_nx^{n-2}+a_{n-1}x^{n-3}+\cdots +a_3x+a_2 \right) x+a_1 \right) x+a_0
\vdots
=\left( \cdots \left( \left( a_nx+a_{n-1} \right) x+a_{n-2} \right) x+\cdots +a_1 \right) x+a_0
我们可以用递推的方式从低到高计算多项式的值。假设有一个函数 f(x)，它表示方程的值。那么，我们从低阶开始计算：
初始化 res = a_0，表示多项式的常数项。
对于每个系数 a_i （从 a_1 到 a_n），更新 res：
res = res \times x + a_i
最终，res 就是多项式在 x 处的值。
这样,题目的方程就转变为一个O(n)复杂度的计算
这种算法又称秦九韶算法
我们只需要枚举x然后计算出来这个式子是否为0就可以判断x是否是方程的解
即代码
bool calcqin(long long x) {
long long sum = 0;
for (long long i=n;i>=1;i--) {
sum=((A[i]+sum)*x)%p;
}
sum=(sum+A[0])% p;
return!sum;
}
那么,题目的a_i数据在10^10000范围内,肯定不好存,于是想到对于f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n=0:
f\left( x \right) \,\,\mathrm{mod} \ p=0 \ \mathrm{mod}\ p
所以在读入时我们可以选择取余1000000007,具体可以见基础 - 对1e9 7取模 - 《算法--ACWing》 - 极客文档
long long read() {//快读
long long sum = 0, fg = 1;
char c = getchar();
while (c<'0'||c>'9') {
if (c=='-')
fg=-1;
c=getchar();
}
while (c>='0'&&c<='9') {
sum=((sum*10)+c-'0')%p;
c=getchar();
}
return sum*fg;
}
最终得到整个代码
#include <bits/stdc++.h>
using namespace std;
const int p=1000000007;
bool flag = true;
int n, m, ans, cnt;
int A[103], key[1000003];
long long read() {//快读
long long sum = 0, fg = 1;
char c = getchar();
while (c<'0'||c>'9') {
if (c=='-')
fg=-1;
c=getchar();
}
while (c>='0'&&c<='9') {
sum=((sum*10)+c-'0')%p;
c=getchar();
}
return sum*fg;
}
void print(int x) {//输出
if (x<0) {
putchar('-');
x=-x;
}
if (x>9) {
print(x/10);
}
putchar(x%10+'0');
}
bool calcqin(long long x) {//计算
long long sum = 0;
for (long long i=n;i>=1;i--) {
sum=((A[i]+sum)*x)%p;
}
sum=(sum+A[0])% p;
return !sum;//如果结果为0，则返回1，否则返回0
}
int main() {
n = read();
m = read();
for (long long i=0;i<=n;i++) {
A[i]= read();//读入a0---an
}
for (long long i=1;i<=m;i++) {
if (calcqin(i)) {//如果运算结果为0
flag=false;
ans++;
key[++cnt]=i;//保存答案
}
}
if (flag) {//如果到最后也没找到答案
cout <<ans<< endl;
return 0;
}
//以下为答案输出
print(ans);
printf("\n");
for (long long i=1;i<=cnt;i++) {
print(key[i]);
printf("\n");
}
return 0;
}
参考:https://www.alipan.com/s/ivjwkwEpYPA
健康查询