C++(g++ 7.5.0) 解法, 执行用时: 518ms, 内存消耗: 512K, 提交时间: 2022-08-18 18:11:32

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
  
int main() {
    int n, p;
    cin >> n >> p;
    vector<int> a(n + 1);
    for(int i = 0; i <= n; ++i) cin >> a[i];
    vector<int> ans;
    for(int i = 0; i < p; ++i) {
        int f = 1;
        while(f) {
            f = 0;
            int cur = a.back();
            vector<int> nxt;
            for(int j = a.size() - 1; j >= 1; --j) {
                nxt.push_back(cur);
                cur = ((a[j - 1] - cur * i) % p + p) % p;
            }
            reverse(nxt.begin(), nxt.end());
            if(cur == 0) {
                f = 1;
                a = nxt;
                ans.push_back(i);
            }
        }
    }
    for(int i : ans) cout << i << " "; cout << '\n';
}

C++ 解法, 执行用时: 486ms, 内存消耗: 436K, 提交时间: 2021-11-21 16:48:36

#include<stdio.h>
#include<iostream>
using namespace std;
const int N=5010;
int n,p,a[N];
int get_poly(int x){
    int pow=1,res=0;
    for(int i=0;i<=n;i++){
        res=(res+a[i]*pow)%p;
        pow=(pow*x)%p;
    }
    return res;
}
int main(){
    scanf("%d%d",&n,&p);
    for(int i=0;i<=n;i++)scanf("%d",&a[i]);
    int ans=p;
    while(n){
        while(get_poly(ans))ans--;
        int k=p-ans;
        printf("%d ",k);
        for(int i=n-1;i>=0;i--)
            a[i]=((a[i]-k*a[i+1])%p+p)%p;
        for(int i=0;i<n;i++)a[i]=a[i+1];
        n--;
    }
    return 0;
}