題目描述

已知多項(xiàng)式方程：

a0+a1x+a2x^2+..+anx^n=0

求這個(gè)方程在[1, m ] 內(nèi)的整數(shù)解（n 和m 均為正整數(shù)）

輸入輸出格式

輸入格式：

輸入文件名為equation .in。

輸入共n + 2 行。

第一行包含2 個(gè)整數(shù)n 、m ，每兩個(gè)整數(shù)之間用一個(gè)空格隔開。

接下來的n+1 行每行包含一個(gè)整數(shù)，依次為a0,a1,a2..an

輸出格式：

輸出文件名為equation .out 。

第一行輸出方程在[1, m ] 內(nèi)的整數(shù)解的個(gè)數(shù)。

接下來每行一個(gè)整數(shù)，按照從小到大的順序依次輸出方程在[1, m ] 內(nèi)的一個(gè)整數(shù)解。

輸入輸出樣例

輸入樣例#1：
2 10 1 -2 1 輸出樣例#1：
1 1 輸入樣例#2：
2 10 2 -3 1 輸出樣例#2：
2 1 2 輸入樣例#3：
2 10 1 3 2 輸出樣例#3：
0

說明

對(duì)于30%的數(shù)據(jù):0<n<=2,|ai|<=100,an!=0,m<100

對(duì)于50%的數(shù)據(jù):0<n<=100,|ai|<=10^100,an!=0,m<100

對(duì)于70%的數(shù)據(jù):0<n<=100,|ai|<=10^10000,an!=0,m<10000

對(duì)于100%的數(shù)據(jù):0<n<=100,|ai|<=10^10000,an!=0,m<1000000

?

題解：
具體不是很清楚啊......

抄了抄代碼而已......

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <iostream> 7 #define ll long long 8 using namespace std; 9 10 const int maxn = 110; 11 const int maxm = 1000010; 12 13 int n,m; 14 int mod[5]={11261,19997,22877,21893,14843}; 15 int a[maxn][5],ans[maxm],pre[maxn][5],res[maxm][5]; 16 char s[10010]; 17 18 int cal(int x, int j) { 19 int sum=0; 20 for(int i=0; i<=n; i++) sum=(sum+pre[i][j]*a[i][j])%mod[j]; 21 if(sum<0) sum+=mod[j];//處理模后負(fù)數(shù)，%+% 22 return sum; 23 } 24 25 bool check(int x) { 26 for(int j=0; j<5; j++) 27 if(res[x%mod[j]][j]) return 0; 28 return 1; 29 } 30 31 int main() { 32 scanf("%d%d", &n, &m); 33 for(int i=0; i<=n; i++) { 34 scanf("%s", s); 35 int ls=strlen(s); bool flg=0; 36 for(int j=0; j<5; j++) 37 if(s[0]=='-') flg=1; 38 else a[i][j]=s[0]-'0'; 39 for(int j=0; j<5; j++) { 40 for(int l=1; l<ls; l++) a[i][j]=(a[i][j]*10+s[l]-'0')%mod[j]; 41 if(flg) a[i][j]=-a[i][j]; 42 } 43 } 44 for(int j=0; j<5; j++) { 45 pre[0][j]=1; 46 for(int x=1; x<mod[j]; x++) { 47 for(int i=1; i<=n; i++) 48 pre[i][j]=(pre[i-1][j]*x)%mod[j]; 49 res[x][j]=cal(x,j); 50 } 51 } 52 for(int i=1; i<=m; i++) 53 if(check(i)) ans[++ans[0]]=i; 54 printf("%d\n", ans[0]); 55 for(int i=1; i<=ans[0]; i++) 56 printf("%d\n", ans[i]); 57 return 0; 58 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/HLXZZ/p/7266893.html

總結(jié)

以上是生活随笔為你收集整理的[NOIP2014] 解方程的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。