首页 > 代码库 > P2312 解方程
P2312 解方程
题目描述
已知多项式方程：
a0+a1x+a2x^2+..+anx^n=0
求这个方程在[1, m ] 内的整数解（n 和m 均为正整数）
输入输出格式
输入格式：
输入文件名为equation .in。
输入共n + 2 行。
第一行包含2 个整数n 、m ，每两个整数之间用一个空格隔开。
接下来的n+1 行每行包含一个整数，依次为a0,a1,a2..an
输出格式：
输出文件名为equation .out 。
第一行输出方程在[1, m ] 内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m ] 内的一个整数解。
输入输出样例
输入样例#1：
2 10 1-21
输出样例#1：
11
输入样例#2：
2 102-31
输出样例#2：
212
输入样例#3：
2 10 1 3 2
输出样例#3：
0
说明
30%:0<n<=2,|ai|<=100,an!=0,m<100
50%:0<n<=100,|ai|<=10^100,an!=0,m<100
70%:0<n<=100,|ai|<=10^10000,an!=0,m<10000
100%:0<n<=100,|ai|<=10^10000,an!=0,m<1000000
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>using namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int mod[5]={11261,19997,22877,21893,14843};int n,m;int ans[1000005];int a[5][105],pre[5][105],res[5][30005];char ch[10005];inline int cal(int t,int x){ int sum=0; for(int i=0;i<=n;i++) sum=(sum+a[t][i]*pre[t][i])%mod[t]; if(sum<0)sum+=mod[t]; return sum;}inline bool jud(int x){ for(int t=0;t<5;t++) if(res[t][x%mod[t]]!=0)return 0; return 1;}int main(){ n=read();m=read(); for(int i=0;i<=n;i++) { scanf("%s",ch+1); int l=strlen(ch+1); bool flag=0; for(int t=0;t<5;t++) if(ch[1]!=‘-‘)a[t][i]=ch[1]-‘0‘; else a[t][i]=0,flag=1; for(int t=0;t<5;t++) { for(int k=2;k<=l;k++) a[t][i]=(a[t][i]*10+ch[k]-‘0‘)%mod[t]; if(flag)a[t][i]=-a[t][i]; } } for(int t=0;t<5;t++) for(int x=1;x<mod[t];x++) { pre[t][0]=1; for(int i=1;i<=n;i++)pre[t][i]=(pre[t][i-1]*x)%mod[t]; res[t][x]=cal(t,x); } for(int i=1;i<=m;i++) if(jud(i))ans[++ans[0]]=i; printf("%d\n",ans[0]); for(int i=1;i<=ans[0];i++) printf("%d\n",ans[i]); return 0;}
P2312 解方程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。