好我终于在校内oj上过了那么为什么提交RE了呢
查看原帖
好我终于在校内oj上过了那么为什么提交RE了呢
157598
Magallan_forever楼主2020/8/14 15:53
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
const int mod=998244353;
int gcd(int a,int b) { return b?gcd(b,a%b):a; }
int fp(long long a,int b,int mod){
    long long ans=1;
    for(a%=mod;b;b>>=1,a=a*a%mod) ans=(b&1?ans*a%mod:ans);
    return ans;
}
int n,a[101];
vector<int> ap,an;
struct node{
    int p,q;
    bool operator<(const node& a) const { return p*a.q<q*a.p; }
};
vector<node> ans;
void get_div(int num,vector<int>& div){
    for(int i=1;i*i<=num;++i)
        if(num%i==0){
            div.push_back(i);
            if(i!=num/i) div.push_back(num/i);
        }
}
bool calc(long long p,long long q){
    long long x=p*fp(q,mod-2,mod)%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;
}
signed main(){
    int temp;
    scanf("%lld",&n);
    for(int i=0;i<=n;++i) scanf("%lld",a+i);
    while(a[temp]==0) ++temp;
    get_div(abs(a[temp]),ap),get_div(abs(a[n]),an);
    for(int i=0;i<ap.size();++i)
        for(int j=0;j<an.size();++j)
            if(gcd(ap[i],an[j])==1){
                if(calc(ap[i],an[j])) ans.push_back((node){ap[i],an[j]});
                if(calc(-ap[i],an[j])) ans.push_back((node){-ap[i],an[j]});
            }
    if(calc(0,1)) ans.push_back((node){0,1});
    sort(ans.begin(),ans.end()),printf("%lld\n",ans.size());
    for(int i=0;i<ans.size();++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;
}
2020/8/14 15:53
加载中...