P4598 [HEOI2012] Akai 的数学作业
设一个解为 \(x=\dfrac{p}{q}\)，满足 \(p,q\) 互质。由定义有 \(\displaystyle\sum_{i=0}^n a_i(\dfrac{p}{q})^i=0\)。
仿照这道题的做法，可以将这个条件放在模意义下判断。
但所有可能的解有很多，考虑分析条件的限制减少枚举量。
通分得到 \(\displaystyle\sum_{i=0}^n a_ip^iq^{n-i}=0\)，肯定也有 \(\displaystyle\sum_{i=0}^n a_ip^iq^{n-i}\equiv 0\pmod p\)。
由于 \(\displaystyle\sum_{i=1}^n a_ip^iq^{n-i}\equiv 0\pmod p\)，那么一定有 \(a_0q^n\equiv 0\pmod p\)。再由 \(p,q\) 互质可得 \(p\mid a_i\)，也就是说分子 \(p\) 只需枚举 \(a_0\) 的因数。
同理可得 \(q\mid a_n\)，\(q\) 只需枚举 \(a_n\) 的因数。
但还存在一个小问题：存在 \(a_0=0\) 的情况。
此时必定存在根 \(x=0\)，其余情况可以给原方程整体除掉 \(x\)，\(a_1\) 变成新方程的 \(a_0\)。
如果 \(a_1=0\) 的话那么可以继续使用上面的方式，由于保证 \(a_n\ne 0\) 必定存在一个非 \(0\) 数。
时间复杂度为 \(\mathcal O(n\max_{i=1}^V d(i)^2)\)，其中 \(d(x)\) 为 \(x\) 的因数个数。
在实现上要注意考虑负数的情况。
#include<bits/stdc++.h>
#define N 105
using namespace std;
vector<int>dp,dq;
int n,a[N],P[N],Q[N];
const int M=998244353;
struct frac{int p,q;bool operator<(const frac &x){return 1ll*p*x.q<1ll*x.p*q;}
};vector<frac>ans;
vector<int>divs(int x){vector<int>d;x=abs(x);for(int i=1;i*i<=x;i++)if(!(x%i)){if(i*i^x)d.emplace_back(x/i),d.emplace_back(-x/i);d.emplace_back(i);d.emplace_back(-i);}return d;
}
int main(){scanf("%d",&n),P[0]=Q[0]=1;for(int i=0;i<=n;i++) scanf("%d",a+i);dq=divs(a[n]);for(int i=0;i<=n;i++) if(a[i]){dp=divs(a[i]);break;}dp.emplace_back(0);for(auto p:dp) for(auto q:dq)if(abs(__gcd(p,q))==1&&q>0){int res=0;for(int i=1;i<=n;i++)P[i]=1ll*P[i-1]*p%M,Q[i]=1ll*Q[i-1]*q%M;for(int i=0;i<=n;i++)res=(res+1ll*a[i]*P[i]%M*Q[n-i])%M;if(!res) ans.push_back({p,q});}printf("%zu\n",ans.size());sort(ans.begin(),ans.end());for(auto x:ans)if(x.q==1) printf("%d\n",x.p);else printf("%d/%d\n",x.p,x.q);return 0;
}