首页 > 代码库 > 洛谷 P2312 解方程
洛谷 P2312 解方程
题目描述
已知多项式方程：
$a_0+a_1x+a_2x^2+..+a_nx^n=0$//用LaTex好看多了
求这个方程在[1, m ] 内的整数解（n 和m 均为正整数）
输入输出格式
输入格式：
输入文件名为equation .in。
输入共n + 2 行。
第一行包含2 个整数n 、m ，每两个整数之间用一个空格隔开。
接下来的n+1 行每行包含一个整数，依次为a0,a1,a2..an
输出格式：
输出文件名为equation .out 。
第一行输出方程在[1, m ] 内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m ] 内的一个整数解。
输入输出样例
2 10 1-21
11
2 102-31
212
2 10 1 3 2
0
说明//题库里的数据范围好丑
30%:$0<n<=2,|a_i|<=100,a_n!=0,m<100$
50%:$0<n<=100,|a_i|<=10^100,a_n!=0,m<100$
70%:$0<n<=100,|a_i|<=10^10000,a_n!=0,m<10000$
100%:$0<n<=100,|a_i|<=10^10000,a_n!=0,m<1000000$
解题思路
枚举有点BSGS的思想，验证有点哈希的味道。
首先可以想到枚举x，看看$f(x)%p$（p要取多个）是否都等于0，如果对于所有p膜模得的数都是0，那么x就是一个解了。选哪些质数来膜模？考验人品……
那么从1到$p_0-1$枚举x，如果$f(x)%p!=0$，那么$f(x+p_0)%p_0!=0$，这样就能去掉许多无用的数，对于$f(x)%p_0==0$的x，再验证$f(x)%p_1$是否为零，如果依然为零(不放心可以多模几个，我只模了2个)，那x多半就是了，然后依次验证$x+p_0$、$x+2*p_0$、$x+3*p_0$……直到m。
计算$f(x)$要用秦九韶算法(或者叫做霍纳法则……)
源代码
#include<stdio.h>#include<string.h>char s[100010]={0};int n,m;int prime[]={10007,1000000207};long long a[105][5]={0};bool is_result[1000010]={0};void quyu(int k)//k为次数{ for(int i=0;i<2;i++) { bool fu=0; int j=0; if(0[s]==‘-‘) j++,fu=1; int len=strlen(s); for(;j<len;j++) a[k][i]=(a[k][i]*10LL%prime[i]+s[j]-‘0‘)%prime[i]; if(fu) a[k][i]=(prime[i]-a[k][i])%prime[i]; }}bool judge(int x,int p)//x取值和质数下标{ long long fx=a[n][p]; for(int i=n-1;i>=0;i--) { fx*=x; fx%=prime[p]; fx+=a[i][p]; fx%=prime[p]; } return fx==0;}int main(){ //freopen("equationa.in","r",stdin); //freopen("equationa.out","w",stdout); scanf("%d%d\n",&n,&m); for(int i=0;i<=n;i++) { scanf("%s",s); quyu(i);//系数还是高精度的…… } for(int i=1;i<=prime[0];i++) { if(!judge(i,0)) continue; for(int j=i;j<=m;j+=prime[0]) { bool ok=1; if(!judge(j,1)) ok=0; if(ok) is_result[j]=1; } } int num=0; for(int i=1;i<=m;i++) if(is_result[i]) num++; printf("%d\n",num); for(int i=1;i<=m;i++) if(is_result[i]) printf("%d\n",i); return 0;}
AC了这题我noip2014就500+分了(*^__^*) 嘻嘻……
洛谷 P2312 解方程