洛谷P2312 [NOIP2014 提高组] 解方程 题解
题意:
已知多项式方程:
\[ 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]\) 内的一个整数解。
数据范围:
\(0<n\le 100,|a_i|\le 10^{10000},a_0\ne 0,m<10^6\) 。
这个题有点哈希的味道。注意到对于质数 \(p\) , \[ a_0+a_1x+a_2x^2+\cdots+a_nx^n\equiv 0 \pmod{p} \] 是原命题成立的一个必要不充分条件,不过在绝大多数情况下都是充分的。
那么我们随便取两个 \(p_1,p_2\)
模一模,看看是不是都为 \(0\)
就好啦,这种情况下出错的概率低到难以置信。
然后就被卡常了。
注意到 \(p^k\) 的个数远小于其他的数的数量,又因为 \[ f(x) \equiv 0 \pmod{p} \quad\Rightarrow\quad f(x + kp)\equiv 0\pmod {p} \] 所以我们可以取一个比较小的 \(p_1\) ,比如 \(10007\) ,然后预处理出哪些 \(x\) 可能有解
这样就不用跑两遍大常数的 \(\mathcal{O}(nm)\) 了。
代码:
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(233))
#define M ((int)(2e5 + 15))
const int p1 = 10007;
const int p2 = 998244853;
char s[M], vis[M];
int n, a[N], b[N], ans[N];
bool calc(const int x, int *arr, const int p)
{
ll sum = 0;
for(int i = n; i; i--) sum = (sum + arr[i]) * x % p;
return !((sum + arr[0]) % p);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int m; cin >> n >> m;
for(int i = 0; i <= n; i++)
{
cin >> (s + 1);
ll x = 0, y = 0; bool f = (s[1] == '-');
for(int j = 1 + f; s[j]; j++)
{
x = (x * 10 + s[j] - '0') % p1;
y = (y * 10 + s[j] - '0') % p2;
}
a[i] = f ? p1 - x : x, b[i] = f ? p2 - y : y;
}
int tot = 0;
for(int i = 0; i < p1; i++) if(calc(i, a, p1)) vis[i] = true;
for(int i = 1; i <= m; i++)
if(vis[i % p1] && calc(i, b, p2)) ans[++tot] = i;
if(!tot) return cout << 0 << '\n', 0;
cout << tot << '\n';
for(int i = 1; i <= tot; i++) cout << ans[i] << '\n';
return 0;
}
题外话:
最近没找什么图片。