题解

思路概述

• 需要检查多项式 P(x)=a_0+a_1x+…+a_nx^n 在区间 [1,m] 内的整数根。直接套用霍纳法即可：P(x)=(((a_n x + a_{n-1}) x + …) x + a_0)。
• 系数与中间值可能非常大，代码对所有计算都取模 mod = 998244353377（接近 1e12 的质数）并使用 __int128 防止乘法溢出；若 P(x) 在该模下也为 0，则视为原方程的整数解。
• 遍历 x=1…m，凡是 check(x) 返回 1 的即加入答案数组。

复杂度

• 对于每个 x 的多项式求值是 O(n)，整体复杂度 O(nm)。由于 m 最大约 1e5，本做法恰好可以通过。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1000005],ans[1000005],cnt,mod=998244353377;
void read(int x){
	string t;
	int tmp=0,f=0;
	cin>>t;
	if(t[0]=='-') f=1;
	for(int i=f; i<t.size(); i++){
		tmp=tmp*10+t[i]-'0';
		tmp%=mod;
	}
	if(!f) a[x]=tmp;
	else a[x]=0-tmp;
}
bool check(int x){
	__int128 t=0;
	for(int i=n; i>=0; i--){
		t*=x;
		t+=a[i];
		t%=mod;
	}
	if(t==0) return 1;
	return 0;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m;
	for(int i=0; i<=n; i++){
		read(i);
	}
	for(int i=1; i<=m; i++){
		if(check(i)){
			ans[++cnt]=i;
		}
	}
	cout<<cnt<<'\n';
	for(int i=1; i<=cnt; i++) cout<<ans[i]<<'\n';
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}