自动搬运

查看原文

来自洛谷，原作者为

	nekko **

搬运于2025-08-24 22:01:48，当前版本为作者最后更新于2018-11-22 19:24:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $x=\frac{p}{q}$，且 $\gcd(p,q)=1$，则有：

通分得：

在模 $p$ 意义下有：

$\begin{aligned}&\because \gcd(p,q)=1 \\ &\therefore p \mid a_0 \end{aligned}$

在模 $q$ 意义下有：

$\begin{aligned}&\because \gcd(p,q)=1 \\ &\therefore q \mid a_n \end{aligned}$

当然如果 $a_0=0$ 的话需要找到一个最小的 $t$ 满足 $a_t \not= 0$

然后就可以枚举 $p \mid a_0, q \mid a_n$ 了，然后暴力判断是否可行

判断的方法和 P2312 解方程 这道题一样，即放到模 $mod$ 剩余系下判断是否为 $0$

时间复杂度：$O(\sqrt a_0 + \sqrt a_n + \sigma_0(a_0)\sigma_0(a_n)\gcd(\max(a_0,a_n)))$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 110, mod = 1e9 + 7;
int n, a[N];

ll pw(ll a, ll b) {
    ll r = 1;
    for( ; b ; b >>= 1, a = a * a % mod)
        if(b & 1)
            r = r * a % mod;
    return r;
}

ll calc(ll p, ll q) {
    ll x = p * pw(q, mod - 2) % mod, pro = 1, res = 0;
    for(int i = 0 ; i <= n ; ++ i) {
        res = (res + pro * a[i] % mod) % mod;
        pro = pro * x % mod;
    }
    return (res + mod) % mod == 0;
}

vector<int> split(int x) {
    x = abs(x);
    vector<int> res;
    for(int i = 1 ; i * i <= x ; ++ i)
        if(x % i == 0) {
            res.push_back(i);
            if(i != x / i) res.push_back(x / i);
        }
    return res;
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b ) : a;
}

struct T { ll p, q; };
vector<T> ans;
bool cmp(T a, T b) {
    return a.p * b.q < a.q * b.p;
}
bool operator == (T a, T b) {
    return a.p == b.p && a.q == b.q;
}

int main() {
    scanf("%d", &n);
    for(int i = 0 ; i <= n ; ++ i) scanf("%d", &a[i]);
    int pos = 0; while(a[pos] == 0) ++ pos;
    vector<int> P = split(a[pos]),
                Q = split(a[n]);
    for(int i = 0 ; i < P.size() ; ++ i) {
        for(int j = 0 ; j < Q.size() ; ++ j) {
            int p = P[i], q = Q[j];
            if(gcd(p, q) == 1) {
                if(calc(p, q)) ans.push_back((T) { p, q });
                if(calc(-p, q)) ans.push_back((T) { -p, q });
            }
        }
    } 
    if(calc(0, 1)) ans.push_back((T) { 0, 1 });
    sort(ans.begin(), ans.end(), cmp);
    printf("%d\n", (int) ans.size());
    for(int i = 0 ; i < ans.size() ; ++ i) {
        ll p = ans[i].p, q = ans[i].q;
        if(q == 1) printf("%lld\n", p);
        else printf("%lld/%lld\n", p, q);
    }
}