https://www.acwing.com/problem/content/517/
给一个多项式，求他的整数根。
首先稳妥的办法应该是整一大堆质数，然后用中国剩余定理合并（当然不是真的合并）。
奇怪一点的就用几个就可以了，卡掉的概率极低，加上是OI其实没问题的。
但是这题卡常，要用秦九韶公式卡掉一半的乘法（和取模），还卡读入，真的垃圾题。
注意读入的时候要%p而不是-p，找到一个写法的bug不错。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXP = 1; const int p = 19260817; int ap[105]; inline int read() { int b = 0; char c = getchar(); while(true) { if(c == '-' || (c >= '0') && (c <= '9')) break; c = getchar(); } if(c == '-') { b = 1; c = getchar(); } int cur = 0; while(c >= '0' && c <= '9') { cur = (cur << 3) + (cur << 1) + (c - '0'); if(cur >= p) cur %= p; c = getchar(); } if(b) cur = (p - cur) % p; return cur; } inline void write(int x) { if(x <= 9) { putchar('0' + x); } else { write(x / 10); putchar('0' + x % 10); } } int ans[1000005]; int atop = 0; int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); #endif // Yinku int n = read(), m = read(); for(int i = 0; i <= n; ++i) ap[i] = read(); for(int x = 1; x <= m; ++x) { ll cur = 0; for(int i = n; i >= 1; --i) { cur = (cur + ap[i]) * x; if(cur >= p) cur %= p; } cur = (cur + ap[0]) % p; if(cur == 0) ans[++atop] = x; } write(atop); putchar('\n'); for(int i = 1; i <= atop; ++i) { write(ans[i]); putchar('\n'); } return 0; }AcWing - 515 - 解方程 = 简单数学
标签：
原文地址：https://www.cnblogs.com/Inko/p/11664463.html