题解 P4598 [HEOI2012]Akai 的数学作业

· · 题解

题意：给你一个一元 n 次方程，请你求出该方程所有的有理数解。

我们设 x=\dfrac{p}{q}(\gcd(p,q)=1)，则原方程可以表示为：

\sum_{k=0}^n a_k\cdot\dfrac{p^k}{q^k}=0

将两边同时乘上 q^n，可以得到：

\sum_{k=0}^n a_k\cdot p^k\cdot q^{n-k}=0

我们发现只有 k=0 时的那一项不一定为 p 的倍数，所以我们可以化简得到：

\sum_{k=0}^n a_k\cdot p^k\cdot q^{n-k}\equiv0\ (\bmod\ p) a_0\cdot q^n\equiv0\ (\bmod\ p)

而由于 \gcd(p,q)=1，所以可以得到 p|a_0，同理我们也可以得到 q|a_n。

所以我们只需要枚举 p 和 q 暴力判断就行了，当 a_0=0 的时候只要不断往后移，直到找到第一个不为 0 的 a_i 就行了，注意特判解为 0 的情况。

由于上式加起来的过程中可能 long long 都存不下，所以我们可以考虑将上式求和的过程中对答案取模一个大质数，如果多个大质数取模后的答案都为 0，则该答案成立。只要选择的数的最小公倍数大于上式的最大值，就不会存在答案不为 0 但是模大质数为 0 了（其实本题随便选几个质数就行了，也不用选那么多），设选的质数个数为 m，则时间复杂度为 \mathcal{O}(nm\sigma_0(a_0)\sigma_0(a_n)\log(\max(a_0,a_n)))。

\mathcal{View\ Code} 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105;
int n, a[N], pr[20], tot;
struct node {int p, q;} ans[N];
vector <int> vp, vq;
inline bool cmp(node a, node b) {
    return a.p * b.q < a.q * b.p;
}
int ksm(int x, int y, int P) {
    int res = 1;
    while(y) {
        if(y & 1) res = res * x % P;
        x = x * x % P, y >>= 1;
    }
    return res;
}
bool check(int p, int q) {
    for(int i = 0; i <= 11; i++) {
        int sum = 0;
        for(int k = 0; k <= n; k++)
            sum = (sum + a[k] * ksm(p, k, pr[i]) % pr[i] * ksm(q, n - k, pr[i]) % pr[i] + pr[i]) % pr[i];
        if(sum != 0) return 0;      
    }
    return 1;
}

signed main() {
    scanf("%lld", &n); for(int i = 0; i <= n; i++) scanf("%lld", &a[i]);
    pr[0] = 998244353, pr[1] = 993244353, pr[2] = 993244853;
    pr[3] = 998244853, pr[4] = 19260817, pr[5] = 1000000007;
    pr[6] = 10000019, pr[7] = 10000079, pr[8] = 10000103;
    pr[9] = 100000471, pr[10] = 100000609, pr[11] = 100000687;
    int pos = 0; while(a[pos] == 0) pos++;
    int a0 = abs(a[pos]), an = abs(a[n]);
    for(int p = 1; p * p <= a0; p++) 
        if(a0 % p == 0) {
            vp.push_back(p);
            if(p != a0 / p) vp.push_back(a0 / p);
        }
    for(int q = 1; q * q <= an; q++)
        if(an % q == 0) {
            vq.push_back(q);
            if(q != an / q) vq.push_back(an / q);
        }
    for(auto p : vp) for(auto q : vq) {
        if(__gcd(p, q) == 1) {
            if(check(p, q)) ans[++tot] = (node){p, q};
            if(check(-p, q)) ans[++tot] = (node){-p, q};
        }
    }
    if(check(0, 1)) ans[++tot] = (node){0, 1};
    sort(ans + 1, ans + 1 + tot, cmp);
    printf("%lld\n", tot);
    for(int i = 1; i <= tot; i++) 
        if(ans[i].q == 1) printf("%lld\n", ans[i].p);
        else printf("%lld/%lld\n", ans[i].p, ans[i].q);
    return 0;
}