P2312 解方程


题意简述:

已知方程:$a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$求该方程在$[1,m]$内的正整数解

$(0<n\leq100,m\leq10^6,|a_i|\leq10^{10000})$

题解:

首先看到那么大的$a_i$自然想到模数处理 因为$a_ix^i=0$的话在模p的情况下也等于0 但注意这个逆命题是不成立的 不过我们选择适当的质数就可以使判错的可能尽可能小 一般我们会采取两到三个模数来提高准确率不过这道题一个模数就能AC了

由于数据非常大 所以我们可以考虑魔改快读 在快读读入数字的不断模p 这样最后得到的结果就是整体模p后的结果 之后在计算式子模p是否为0时我们可以采用秦九韶算法使得在$O(n)$计算出该方程的值 我们挨个枚举$m$来判断 因此时间复杂度为$O(nm)$

下面来简单介绍一下秦九韶算法:

$a_0+a_1x+a_2x^2+\cdots+a_nx^n$

$=a_0+x(a_1+a_2x+\cdots+a_nx^{n-1})$

$=a_0+x(a1+x(a_2+a_3x+\cdots+a_nx^{n-2}))$

$\cdots\cdots\cdots\cdots$

$=a_0+x(\cdots+x(a_{n-1}+xa_n))$

所以我们可以一开始令方程的答案$ans=0$每次都$ans=ans\cdot x+a_i$这样我们就可以线性算出方程的值

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
const int p=1e9+7;
const int maxn=1000010;
ll a[maxn],n,m,res[maxn],num;
ll read()
{
    ll x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();};
    while(ch>='0'&&ch<='9') x=(x*10+ch-'0')%p,ch=getchar();
    return x*t;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++)
    {
        ll ans=0;
        for(int t=n;t>=1;t--) ans=(ans+a[t])*i%p;
        if((ans+a[0])%p==0) res[++num]=i;
    }
    printf("%d\n",num);
    for(int i=1;i<=num;i++) printf("%d\n",res[i]);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
AtCoder Beginner Contest 145 AtCoder Beginner Contest 145
第一次AtCoder体验 A.Circle开场送温暖 int main() { int r;cin>>r; cout<<r*r<<endl; return 0; } B.Echo直接判断前
2019-11-17
下一篇 
CF1239A Ivan the Fool and the Probability Theory CF1239A Ivan the Fool and the Probability Theory
题意简述:给定一个 $n\cdot m$ 的方格图,每个格子可以被染成黑色或白色,且与其相邻的四个格子中至多只有一个与其颜色相同,求方案数。 题解:我们可以一行一行的考虑 首先假如第一行存在连续的两个1 那么后面的状态就全部可以推出 因为
2019-11-15
  目录