洛谷 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+分了(*^__^*) 嘻嘻……