洛谷P4598 解高次方程，数论

题意：

给出序列$[a_0,a_2,a_3,...,a_n]$，求方程
$$a_0+a_{1}x+a_2{x}^2+...+a_n{x}^n=0$$
的所有有理数解

Solution：

设$x=\frac{p}{q}$是一个解，并且$gcd(p,q)=1$，代入得到
$$\sum _{i=0}^n{a}_i(\frac{p}{q}{)}^i=0$$
通分得到
$$\sum _{i=0}^n{a}_i{p}^i{q}^{n-i}=0$$
在模$p$时，有
$$\sum _{i=0}^n{a}_i{p}^i{q}^{n-i}\equiv 0(modp)\Rightarrow a_0{q}^n\equiv 0(modp)$$
在模$q$时，有
$$\sum _{i=0}^n{a}_i{p}^i{q}^{n-i}\equiv 0(modq)\Rightarrow a_n{p}^n\equiv 0(modq)$$
由于$gcd(p,q)=1$，于是一定存在
$$p|a_0,q|a_n$$
只需要枚举$a_0,a_n$的因子分别作为$p,q$，然后检查原式是否成立即可。原式可能非常大，一种检验的方法是在多模数下运算值都为$0$

// #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=105,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod1=1e9+7,mod2=1e9+9;

template<class T>
T abs(T x){return x>=0?x:-x;}

int n,a[N];
vector<pair<int,int>>ans;

ll qpow(ll a,ll b,ll mod)
{
    ll ret=1,base=a;
    while(b)
    {
        if(b&1) ret=ret*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ret;
}

ll qm(ll x,ll mod)
{
    return (x%mod+mod)%mod;
}

bool check(int p,int q,ll mod)
{
    ll ret=0;
    for(int i=0;i<=n;i++) ret=(ret+qm(1ll*a[i]*qpow(p,i,mod)%mod*qpow(q,n-i,mod)%mod,mod))%mod;
    return ret==0;
}

void solve(int p,int q)
{
    int tmp=__gcd(abs(p),abs(q));
    p/=tmp; q/=tmp;
    if(check(p,q,mod1)&&check(p,q,mod2)) ans.push_back(make_pair(p,q));
}

int main()
{
    #ifdef stdjudge
        freopen("in.txt","r",stdin);
    #endif
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==0) n--,i--,ans.push_back(make_pair(0,1));
    }
    for(int i=1,limit1=sqrt(abs(a[0]));i<=limit1;i++)
    {
        if(a[0]%i) continue;
        for(int j=1,limit2=sqrt(abs(a[n]));j<=limit2;j++)
        {
            if(a[n]%j||__gcd(i,j)!=1) continue;
            solve(i,j); solve(-i,j);
            solve(a[0]/i,j); solve(-a[0]/i,j);
            solve(i,a[n]/j); solve(-i,a[n]/j);
            solve(a[0]/i,a[n]/j); solve(-a[0]/i,a[n]/j);
        }
    }
    for(auto i:ans)
    {
        if(i.first<0&&i.second<0) i.first=-i.first,i.second=-i.second;
        else if(i.second<0) i.first=-i.first,i.second=-i.second;
    }
    sort(ans.begin(),ans.end(),[&](pair<int,int>&x,pair<int,int>&y){
        return 1.0*x.first/x.second<1.0*y.first/y.second;
    });
    ans.erase(unique(ans.begin(),ans.end(),[&](pair<int,int>&x,pair<int,int>&y){
        return fabs(1.0*x.first/x.second-1.0*y.first/y.second)<1e-8;
    }),ans.end());
    cout<<ans.size()<<endl;
    for(auto i:ans)
    {
        if(i.first<0&&i.second<0) i.first=-i.first,i.second=-i.second;
        else if(i.second<0) i.first=-i.first,i.second=-i.second;
        if(i.second>1) printf("%d/%d\n",i.first,i.second);
        else printf("%d\n",i.first);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96