P2312 解方程

题意简述:

已知方程:$a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$求该方程在$[1,m]$内的正整数解

$(0<n\leq100,m\leq10^6,|a_i|\leq10^{10000})$

题解:

首先看到那么大的$a_i$自然想到模数处理 因为$a_ix^i=0$的话在模p的情况下也等于0 但注意这个逆命题是不成立的 不过我们选择适当的质数就可以使判错的可能尽可能小 一般我们会采取两到三个模数来提高准确率不过这道题一个模数就能AC了

由于数据非常大 所以我们可以考虑魔改快读 在快读读入数字的不断模p 这样最后得到的结果就是整体模p后的结果 之后在计算式子模p是否为0时我们可以采用秦九韶算法使得在$O(n)$计算出该方程的值 我们挨个枚举$m$来判断 因此时间复杂度为$O(nm)$

下面来简单介绍一下秦九韶算法:

$a_0+a_1x+a_2x^2+\cdots+a_nx^n$

$=a_0+x(a_1+a_2x+\cdots+a_nx^{n-1})$

$=a_0+x(a1+x(a_2+a_3x+\cdots+a_nx^{n-2}))$

$\cdots\cdots\cdots\cdots$

$=a_0+x(\cdots+x(a_{n-1}+xa_n))$

所以我们可以一开始令方程的答案$ans=0$每次都$ans=ans\cdot x+a_i$这样我们就可以线性算出方程的值

AC代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
const int p=1e9+7;
const int maxn=1000010;
ll a[maxn],n,m,res[maxn],num;
ll read()
{
	ll x=0,t=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();};
	while(ch>='0'&&ch<='9') x=(x*10+ch-'0')%p,ch=getchar();
	return x*t;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++)
	{
		ll ans=0;
		for(int t=n;t>=1;t--) ans=(ans+a[t])*i%p;
		if((ans+a[0])%p==0) res[++num]=i;
	}
	printf("%d\n",num);
	for(int i=1;i<=num;i++) printf("%d\n",res[i]);
	return 0;
}