洛谷 P2312 解方程解题报告

P2312 解方程

题目描述

已知多项式方程：

(a_0+a_1x+a_2x^2+cdots+a_nx^n=0)求这个方程在 ([1,m]) 内的整数解（(n) 和 (m) 均为正整数）。

输入输出格式

输入格式：

共 (n + 2) 行。

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

接下来的 (n+1) 行每行包含一个整数，依次为 (a_0,a_1,a_2ldots a_n) 。

输出格式：

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

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

说明

对于 (30\%) 的数据：(0<nle 2,|a_i|le 100,a_n≠0,m<100)。

对于 (50\%) 的数据：(0<nle 100,|a_i|le 10^{100},a_n≠0,m<100)。

对于 (70\%) 的数据：(0<nle 100,|a_i|le 10^{10000},a_n≠0,m<10^4) 。

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

对不完美算法还是不敏感啊

一直想着去优化高精度的复杂度

事实上对(a)模上大质数然后枚举解代入方程秦久韶进行检验即可

复杂度：(O(nm))

Code：

#include <cstdio>
#define ll long long
const ll mod=10260817;
const ll N=103;
ll a[N],n,m;
void read(ll id)
{
    char c=getchar();ll f=1;
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {a[id]=(a[id]*10+c-'0')%mod;c=getchar();}
    a[id]*=f;
}
void init()
{
    scanf("%lld%lld",&n,&m);
    for(ll i=0;i<=n;i++) read(i);
}
ll cnt,ans[N*N*N];
void work()
{
    for(ll i=1;i<=m;i++)
    {
        ll sum=0;
        for(ll j=n;j;j--)
            sum=(sum+a[j])*i%mod;
        (sum+=a[0])%=mod;
        if(!sum) ans[++cnt]=i;
    }
    printf("%lld
",cnt);
    for(ll i=1;i<=cnt;i++) printf("%lld
",ans[i]);
}
int main()
{
    init();
    work();
    return 0;
}

2018.9.1