首页 > 代码库 > 解方程
解方程
传送门
题目描述
已知多项式方程：
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
题解：通过取模来判断等式两边是否成立。如果一个数x对于这个等式成立的话，那么x+mod（模的那个数）也会成立。
#include<cstdio>#include<iostream>#include<cstring>#define M 110#define N 1000010#define ll long longusing namespace std;char s[N];int n,m;ll a[3][M],p[3]={0,10007,1000001397};bool f[N];bool xx(int x,int k){ ll ans=0,w=1; for(int i=0;i<=n;i++) { ans=(ans+a[k][i]*w%p[k])%p[k]; w=(w*x)%p[k]; } if(!(ans%p[k])) return 1; return 0;}int main(){ scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) { scanf("%s",s); int l=strlen(s); bool ff=0; for(int j=1;j<=2;j++) { int x=0; if(s[0]==‘-‘) { ff=1; x=1; } for(int k=x;k<l;k++) a[j][i]=(a[j][i]*10%p[j]+(ll)s[k]-‘0‘)%p[j]; if (ff) a[j][i]=p[j]-a[j][i]; } } for(int i=1;i<=p[1];i++) if(xx(i,1)) { for(int j=i;j<=m;j+=p[1]) if(xx(j,2)) f[j]=1; } int sum=0; for(int i=1;i<=m;i++) if(f[i]) sum++; printf("%d\n",sum); for(int i=1;i<=m;i++) if(f[i]) printf("%d\n",i); return 0;}
解方程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。