題目描述

已知多項式方程：

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 -2 1

輸出樣例#1：

1 1

輸入樣例#2：

2 10 2 -3 1

輸出樣例#2：

2 1 2

輸入樣例#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

分析：一看想是用高精度做，可能還會超時，就沒仔細做，打的暴力枚舉，50分正解：其實不是高精度……對于很大的數，我們可以給它取模，因為等式兩邊取模仍然成立。但是枚舉x來判斷的話會超時，所以這里用到一個技巧：如果一個數x對于這個等式成立的話，那么x+mod（模的那個數）也會成立。需要注意的是，只用一個數模可能會不對，所以多用幾個檢驗一下。代碼: #include<cstdio> #include<iostream> #include<cstring> #define M 110 #define N 1000010 #define ll long long using namespace std; char s[N]; int n,m; ll a[3][M],p[3]={0,10007,1000001397}; bool ok[N]; bool check(int x,int num) {ll ans=0,w=1;for(int i=0;i<=n;i++){ans=(ans+a[num][i]*w%p[num])%p[num];w=(w*x)%p[num];}if(!(ans%p[num]))return true;return false; } int main() {freopen("jh.in","r",stdin);scanf("%d%d",&n,&m);for(int i=0;i<=n;i++){scanf("%s",s);int l=strlen(s);bool flag=false;for(int j=1;j<=2;j++){int x=0;if(s[0]=='-'){flag=true;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(flag)a[j][i]=p[j]-a[j][i];}}for(int i=1;i<=p[1];i++)if(check(i,1)){for(int j=i;j<=m;j+=p[1])if(check(j,2))ok[j]=true;}int tot=0;for(int i=1;i<=m;i++)if(ok[i])tot++;printf("%d\n",tot);for(int i=1;i<=m;i++)if(ok[i])printf("%d\n",i);return 0; } View Code

?

轉載于:https://www.cnblogs.com/harden/p/5785170.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的解方程（codevs 3732）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。