【数论】[涨姿势：同余]P2312解方程

题目描述

已知多项式方程：\(a_0 + a_1x + a_2x^2+...+a_nx^n = 0\)

求这个方程在[1,m]内的整数解

\(1\leq n\leq100,|a_i|\leq 10^{10000},a_n≠0,m\leq 10^6\)

Solution

首先由于数据过大，只能字符串读入了hhh。然后：对于每个x，算出f(x)%pi，如果f(x)=0则f(x)%pi必然=0，多选几个素数，就可以在一定范围大小内判断成功。好像不够快？

\(f(x+p)≡f(x)(mod p)\)

对于一个x，\(f(x)≠0(mod p)\)，则x+p,x+2p……均不为方程的解

有了这个性质就可以瞎搞了。取几个较大的质数搞一搞……

Code

#include <iostream>

#include <cstdio>

using namespace std;

inline long long read() {

  long long x = 0; int f = 0; char c = getchar();

  while (c < '0' || c > '9') f |= c == '-', c = getchar();

  while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();

  return f? -x:x;

}

long long a[110][4], mod[4] = {10007, 11003, 12007, 13001};

int b[1000010], n, m;

string qwq;

bool check(long long x) {

  for (int k = 0; k < 4; k++) {

    long long tmp = a[n][k];

    for (int i = n - 1; i >= 0; i--)

      tmp = (tmp * x + a[i][k]) % mod[k];

    if (tmp) {

      for (int i = x; i <= m; i += mod[k]) b[i] = 1;

      return 0;

    }

  }

  return 1;

}

int main() {

  n = read(); m = read();

  for (int i = 0; i <= n; ++i) {

    cin >> qwq;

    for (int k = 0; k < 4; ++k) {

      long long flg = 1, tmp = 0;

      for (int j = 0; j < qwq.length(); ++j)

        if (qwq[j] == '-') flg = -1;

        else tmp = ((tmp << 1) + (tmp << 3) + (qwq[j] ^ 48)) % mod[k];

        a[i][k] = tmp * flg;

      }

  }

  int ans = 0;

  for (int x = 1; x <= m; x++)

    if (!b[x] && check(x)) ans++;

  printf("%d\n", ans);

  for (int i = 1; i <= m; i++)

    if (!b[i]) printf("%d\n", i);

  return 0;

}

巴特西

【数论】[涨姿势：同余]P2312解方程

Solution

Code

最新文章

热门文章