洛谷 P2312 解方程 解题报告

时间：2021-12-02 16:15:08

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_2\ldots a_n\) 。

输出格式：

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

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

说明

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

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

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

对于 \(100\%\) 的数据：\(0<n\le 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\n",cnt);

    for(ll i=1;i<=cnt;i++) printf("%lld\n",ans[i]);

}

int main()

{

    init();

    work();

    return 0;

}

2018.9.1

相关文章