题解：P2312 [NOIP2014 提高组] 解方程

· · 题解

题目大意

在 1 到 10^6 的范围内解一个看起来很吓人的方程。

分析

对于 100\% 的数据：0<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^6 。

相信你一眼就看到了 |a_i|\le 10^{10000} 的离谱范围，但 m 的范围却相对较小。这是，就会自然而然的想到枚举 x，来逗答案（四川方言，意为挨个试出答案）。

问题来了，怎么逗？

首先，我问先来表示出题干所给的函数值：

f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2 x^2+ a_1x+a_0

显然，若 f(x)=0，则 x 为正确答案。

我们来简化一下 f(x)：

f(x)=a_n x^n+a_{n-1} x^{n-1}+\cdots+a_2 x^2 +a_1x+a_0\\ = (a_nx^{n-1}+a_{n-1}x^{n-2}+\cdots+a_2x+a_1)x+a_0\\ =((a_nx^{n-2}+a_{n-1}x^{n-3}+\cdots+a_2)x+a_1)x+a_0\\ \cdots\\\ =(\cdots((a_nx+a_{n-1})x+\cdots+a_2)x+a_1)x+a_0

我们就可以用 f(x) 分别对两个数（绝对不能有倍数关系，最好都是质数）取模，看是否为 0。于是，我们就能通过下面的代码来检验 x 是否为正确答案：

bool f(int x0,int M,long long *t){//m是模数，t是对应的a数组
    long long res=t[n];
    for(int i=n-1;i>=0;i--) res=(res*x0+t[i])%M;
    return res==0;
}

推到这里，我们就不得不面对 |a_i|\le10^{10000} 的离谱数据。

数值这么大，自然不能用直接读入。我们可以对其进行哈希，利用快读的思想，就能对其进行取模：

for(int i=0;i<=n;i++){//快读应该都会吧？
    long long x=0,X=0;  bool F=false;   char c=getchar();
    while(c<'0'||'9'<c){if(c=='-') F=true;c=getchar();}
    while('0'<=c&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0',X=(X<<3)+(X<<1)+c-'0';
        x%=mod,X%=Mod;//边乘边取模
        c=getchar();
    }
    a[i]=F?mod-x:x,A[i]=F?Mod-X:X;//这里一定要小心，不要直接拿负数取模！
}

code

#include<bits/stdc++.h>
using namespace std;
const int mod=10007,Mod=1e9+7;
int n,m,cnt,ans[100001];
long long a[102],A[102];
bool vis[mod];

bool f(int x0,int M,long long *t){
    long long res=t[n];
    for(int i=n-1;i>=0;i--) res=(res*x0+t[i])%M;
    return res==0;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++){
        long long x=0,X=0;  bool F=false;   char c=getchar();
        while(c<'0'||'9'<c){if(c=='-') F=true;c=getchar();}
        while('0'<=c&&c<='9'){
            x=(x<<3)+(x<<1)+c-'0',X=(X<<3)+(X<<1)+c-'0';
            x%=mod,X%=Mod;
            c=getchar();
        }
        a[i]=F?mod-x:x,A[i]=F?Mod-X:X;
    }
    for(int i=0;i<mod;i++) if(f(i,mod,a)) vis[i]=true;
    for(int i=1;i<=m;i++) if(vis[i%mod]&&f(i,Mod,A)) ans[++cnt]=i;
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]);
    return 0;
}