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

JayJessy · 2024-07-13 15:20:41 · 题解

难道有人看题解不点赞的吗？

别看这道题是蓝题，其实很简单。
当我下滑看到数据范围，先是一高兴。欸！O(nm) 能过！
紧接着便泄了气，救命啊，|a_i|\le 10^{10000}！！
随后便写了 30 分暴力……
然后就默默地点开了题解……

题目解析

• 我们先解决 a_i 很大的问题，可以使用阴间版快读，使用一个 mod=998244353 来取模。不过，保险起见，也可以用两个甚至更多模数。

  ll read() {
  ll f=1,x=0;
  char c=getchar();
  while(c<'0' || c>'9') {
      if(c=='-') f=-1;
      c=getchar();
  }
  while(c>='0' && c<='9') {
      x=(x*10+c-'0')%mod;
      c=getchar();
  }
  return x*f;
  }

• 接下来我们枚举 x，算出 a_0+a_1x+a_2x^2+\cdots+a_nx^n 的值。
  这个过程我们可以使用秦九韶算法。

  ll sum=0;
  for(ll i=n; i>=1; i--) sum=(sum+a[i])*x%mod;
  sum=(sum+a[0])%mod;
  if(!sum) ans[++cnt]=x;

  好啦，这道题就这么多，下面是——

  AC 代码

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const ll N=110,mod=998244353;
  ll n,m,cnt,a[N],ans[N];
  ll read() {
  ll f=1,x=0;
  char c=getchar();
  while(c<'0' || c>'9') {
      if(c=='-') f=-1;
      c=getchar();
  }
  while(c>='0' && c<='9') {
      x=(x*10+c-'0')%mod;
      c=getchar();
  }
  return x*f;
  }
  int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  n=read(),m=read();
  for(ll i=0; i<=n; i++) a[i]=read();
  for(ll x=1; x<=m; x++) {
      ll sum=0;
      for(ll i=n; i>=1; i--) sum=(sum+a[i])*x%mod;
      sum=(sum+a[0])%mod;
      if(!sum) ans[++cnt]=x;
  }
  cout<<cnt<<"\n";
  for(ll i=1; i<=cnt; i++) cout<<ans[i]<<"\n";
  return 0;
  }

  完结撒花~~