题解 【NOIP2014】解方程

题目描述

已知多项式方程：

a0+a1x+a2x2+?+anxn=0a_0+a_1x+a_2x^2+\cdots+a_nx^n=0a0?+a1?x+a2?x2+?+an?xn=0

求这个方程在 [1,m][1,m][1,m] 内的整数解（nnn 和 mmm 均为正整数）。

输入格式：

输入共 n+2n + 2n+2 行。

第一行包含 222 个整数 n,mn, mn,m ，每两个整数之间用一个空格隔开。

接下来的 n+1n+1n+1 行每行包含一个整数，依次为 a0,a1,a2…ana_0,a_1,a_2\ldots a_na0?,a1?,a2?…an? 。

输出格式：

第一行输出方程在 [1,m][1,m][1,m] 内的整数解的个数。

接下来每行一个整数，按照从小到大的顺序依次输出方程在 [1,m][1,m][1,m] 内的一个整数解。

说明

对于 30%30\%30% 的数据：0<n≤2,∣ai∣≤100,an≠0,m<1000<n\le 2,|a_i|\le 100,a_n≠0,m<1000<n≤2,∣ai?∣≤100,an?≠0,m<100 。

对于 50%50\%50% 的数据：0<n≤100,∣ai∣≤10100,an≠0,m<1000<n\le 100,|a_i|\le 10^{100},a_n≠0,m<1000<n≤100,∣ai?∣≤10100,an?≠0,m<100 。

对于 70%70\%70% 的数据：0<n≤100,∣ai∣≤1010000,an≠0,m<1040<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^40<n≤100,∣ai?∣≤1010000,an?≠0,m<104 。

对于 100%100\%100% 的数据：0<n≤100,∣ai∣≤1010000,an≠0,m<1060<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^60<n≤100,∣ai?∣≤1010000,an?≠0,m<106 。

解析

这题的数据看起来似乎特别吓人。。。

但实际上，

这题非常好想。

只需要模一个大质数就行了（我模的是1e9+7）（实测有效）

另外，ａ要用快读读入，再一边模Mod（因为实在太大了）。

然后，秦九韶算法了解一下：

https://baike.baidu.com/item/%E7%A7%A6%E4%B9%9D%E9%9F%B6%E7%AE%97%E6%B3%95/449196

接下来，只需要枚举1～m的所有整数再判断就行了。

然而，这一切并没有结束...

这样的时间复杂度是O（n*m）

所以稍微有点常数就会被卡（惨痛的经验教训），

因此，我们要直接开long long,在最后模一下Ｍｏｄ就行了（不然会被卡）。

上AC代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Mod1=1e9+7,Mod2=1e9+9;
ll n,m,a1[1001],a2[1001];
ll ans[100001];

bool isroot(int x){
    ll ret1=0,ret2=0;
    for(int i=n;i;i--){
        ret1=((ret1+a1[i])*x)%Mod1;
    }
    ret1=(ret1+a1[0])%Mod1;
    return !ret1;
}

void read1(int k){
    ll x1=0,x2=0,f=1;
    char ch=getchar();
    while(ch>‘9‘||ch<‘0‘){
        if(ch==‘-‘) f=-1;
        ch=getchar();
    }
    while(ch<=‘9‘&&ch>=‘0‘){
        x1=(ll)(x1*10+(ch-‘0‘))%Mod1;
        ch=getchar();
    }
    a1[k]=x1*f;
} 

void print(int x){
    if(x<0) putchar(‘-‘),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+‘0‘);
}

int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<=n;i++){
        read1(i);
    }
    for(int i=1;i<=m;i++){
        if(isroot(i)) ans[++ans[0]]=i;
    }
    print(ans[0]);
    printf("\n");
    for(int i=1;i<=ans[0];i++){
        print(ans[i]);
        printf("\n");
    }
    return 0;
}