洛谷 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 ] 内的一個整數解。

輸入輸出樣例

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

說明//題庫裡的資料範圍好醜

30%:$0<n<=2,|a_i|<=100,a_n\not=0,m<100$

50%:$0<n<=100,|a_i|<=10^{100},a_n\not=0,m<100$

70%:$0<n<=100,|a_i|<=10^{10000},a_n\not=0,m<10000$

100%:$0<n<=100,|a_i|<=10^{10000},a_n\not=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+分了(*^__^*) 嘻嘻……