过不了样例求助
查看原帖
过不了样例求助
157598
Magallan_forever楼主2020/8/13 20:50
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
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;
}
int main(){
	int temp;
	scanf("%d",&n);
	for(int i=0;i<=n;++i) scanf("%d",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[i])) ans.push_back((node){ap[i],an[i]});
				if(calc(-ap[i],an[i])) ans.push_back((node){-ap[i],an[i]});
			}
	if(calc(0,1)) ans.push_back((node){0,1});
	sort(ans.begin(),ans.end()),printf("%d\n",ans.size());
	for(int i=0;i<ans.size();++i)
		if(ans[i].q==1) printf("%d\n",ans[i].p);
		else printf("%d/%d\n",ans[i].p,ans[i].q);
	return 0;
}
2020/8/13 20:50
加载中...