[HEOI2012]Akai的数学作业

作业"/>

[HEOI2012]Akai的数学作业

题目地址【IN】

• 题意简述

给你一个多项式方程，形式如下，求其所有的有理数解。

a0+a1x+a2x2+⋯+anxn=0a_0+a_1x+a_2x^2+\cdots+a_nx^n=0a0​+a1​x+a2​x2+⋯+an​xn=0

• 暴力

我们发现输出的是一个分子和分母互质的分数，所以我们枚举一下分子和分母，为了不超时，枚举大概300300300不到，然后每次计算一下（用高精），大概能得到303030分。

• 优化

我们由于用高精，复杂度比较高，所以我们考虑取模意义下，当我们多取几个模数，在这几个模数的意义下，算出来都是000，那么也可以看作是答案，但是有一定错的概率，当模数比较大且为质数时不容易错，大概能拿30∼5030\sim 5030∼50分。

• 分析

我们可以将开始的式子转换为分数形式，我们令x=pqx=\frac{p}{q}x=qp​

那么原式就可以写成：

a0+a1(pq)+a2(pq)2+⋯+an(pq)n=0a_0+a_1\left(\frac{p}{q}\right)+a_2\left(\frac{p}{q}\right)^2+\cdots+a_n\left(\frac{p}{q}\right)^n = 0a0​+a1​(qp​)+a2​(qp​)2+⋯+an​(qp​)n=0
a0+a1(pq)+a2(p2q2)+⋯+an(pnqn)=0a_0+a_1\left(\frac{p}{q}\right)+a_2\left(\frac{p^2}{q^2}\right)+\cdots+a_n\left(\frac{p^n}{q^n}\right) = 0a0​+a1​(qp​)+a2​(q2p2​)+⋯+an​(qnpn​)=0

接下来我们等式两端同时乘以qnq^nqn，那么可以得到如下式子：

a0qn+a1pqn−1+a2p2qn−2+⋯+anpn=0a_0q^n+a_1pq^{n-1}+a_2p^2q^{n-2}+\cdots+a_np^n=0a0​qn+a1​pqn−1+a2​p2qn−2+⋯+an​pn=0

我们将式子两端同时模qqq，那么可以得到：

anpn≡0(mod q)a_np^n\equiv0(\rm mod\ q)an​pn≡0(mod q)

我们可以得到qqq肯定为ana_nan​的因子，因为p,qp,qp,q互质，即q∣anq|a_nq∣an​。

我们再将原式两端同时模ppp，那么同样可以得到：

a0qn≡0(mod p)a_0q^n\equiv0(\rm mod\ p)a0​qn≡0(mod p)

我们同样可以的到ppp肯定为a0a_0a0​的因子，同理，即p∣a0p|a_0p∣a0​

所以我们可得对于方程的解x=pqx=\frac{p}{q}x=qp​，我们就得知了p∣a0p|a_0p∣a0​且q∣anq|a_nq∣an​并且还要满足(p,q)=1(p,q)=1(p,q)=1（也就是题面要求的p,qp,qp,q互质）。

• 正解

有了上面的分析，我们就可以先预处理对于a0a_0a0​和ana_nan​的因子，但是这里有个问题就是如果a0=0a_0=0a0​=0或者an=0a_n=0an​=0，那么我们对于a0a_0a0​就换成左边第一个不为000的系数，a1a_1a1​换成右边第一个不为000的因子（由于系数是000，所以前面的都可以相当于没有）。

然后我们可以枚举p,qp,qp,q，由于2×1072\times 10^72×107的因子数最多为512512512，所以我们可以直接5122512^25122枚举。

对于判断一个解pq\frac{p}{q}qp​是否合法，我们可以取几个模数，然后按照优化的暴力方式判断一个解是否合法（其实有一个非常好的模数，只需这一个500335003350033，就可以判断了）。

然后对于每个枚举的pq\frac{p}{q}qp​，由于有负数的解，所以我们还要对每个枚举的pq\frac{p}{q}qp​去判断−pq-\frac{p}{q}−qp​。

然后我们用一个结构体写一个分数类，将答案存入，并重载小于排序，输出答案即可。

下面上代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int Mod=50033;
const int N=1010,M=110;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int fpow(int a,int b){int ans=1;for(;b;b>>=1,a=(1ll*a*a)%Mod)if(b&1)ans=(1ll*ans*a)%Mod;return ans;}
int in1[N],in2[N],c1,c2;
int A[M],n;
void init(){int a=0,b=0;for(int i=0;i<=n;i++)if(A[i]){a=A[i];break;}for(int i=n;i>=0;i--)if(A[i]){b=A[i];break;}if(a<0)a=-a;if(b<0)b=-b;int t1=sqrt(a),t2=sqrt(b);for(int i=1;i<=t1;i++){if(!(a%i)){in1[++c1]=i;if(a/i!=i)in1[++c1]=a/i;}}sort(in1+1,in1+c1+1);for(int i=1;i<=t2;i++){if(!(b%i)){in2[++c2]=i;if(b/i!=i)in2[++c2]=b/i;}}sort(in2+1,in2+c2+1);
}
struct node{int fz,fm;node(){}node(int a,int b):fz(a),fm(b){}bool operator <(const node &a)const{if((!fz||!fm)||(!a.fz||!a.fm)){if((!fz||!fm)&&(!a.fz||!a.fm)) return 1;if((!fz||!fm))return 0<a.fz;if((!a.fz||!a.fm))return fz<0;}ll t1=1ll*fz*a.fm,t2=1ll*a.fz*fm;return t1<t2;}void out(){if(!fz||!fm) puts("0");else if(fm==1) printf("%d\n",fz);else{int now=gcd(fz,fm);fz/=now;fm/=now;if(fm<0)fz=-fz,fm=-fm;printf("%d/%d\n",fz,fm);}}
}anss[M];
int tot;
void calc(int type,int p,int q){int ans=0,t1=1,t2=1,inv_q=fpow(q,Mod-2)%Mod;if(type)p=-p;for(int i=1;i<=n;i++)t1=(t1*q)%Mod;for(int i=0;i<=n;i++){ans=(ans+1ll*A[i]*t1%Mod*t2%Mod)%Mod;t1=(1ll*t1*inv_q)%Mod;t2=(1ll*t2*p)%Mod;}if(!ans){anss[++tot]=node(p,q);}else return;
}
int main(){scanf("%d",&n);for(int i=0;i<=n;i++)scanf("%d",&A[i]);init();for(int i=0;i<=n;i++)A[i]%=Mod;for(int i=1;i<=c1;i++){for(int j=1;j<=c2;j++){if(gcd(in1[i],in2[j])==1){calc(0,in1[i],in2[j]);calc(1,in1[i],in2[j]);}}}if(A[0]==0)anss[++tot]=node(0,0);sort(anss+1,anss+tot+1);printf("%d\n",tot);for(int i=1;i<=tot;i++)anss[i].out();return 0;
}

下面为hdxrie\rm hdxriehdxrie的讲解OrzOrzOrz：

复数域下的一个关于xxx的nnn次多项式f(x)=a0+a1x+a2x2+a3x3+...+anxnf(x)=a_0+a_1x+a_2x^2+a_3x^3+...+a_nx^nf(x)=a0​+a1​x+a2​x2+a3​x3+...+an​xn一定可以分解成nnn个含xxx的一次多项式相乘，即f(x)f(x)f(x)一定存在一种形如f(x)=∏(bix+ci)f(x)=\prod(b_ix+c_i)f(x)=∏(bi​x+ci​)的表示，其中每个式子都会产生一个复数域下的根（当然，这些根有可能重复）。

我们只用考虑有理数根，所以可以把方程改写为f(x)=g(x)×∏(bix+ci)f(x)=g(x)\times\prod(b_ix+c_i)f(x)=g(x)×∏(bi​x+ci​)的样子，其中g(x)g(x)g(x)是一个关于xxx的多项式，包含了所有的非有理数根，剩下的部分就表示了所有的有理数根。令g(x)g(x)g(x)的常数项为www，最高次项的系数为rrr，则原方程的最高次项的系数an=r∏bia_n=r\prod b_ian​=r∏bi​，常数项a0=w∏cia_0=w\prod c_ia0​=w∏ci​，所以对于一个有理数解−cibi\frac{-c_i}{b_i}bi​−ci​​，cic_ici​为a0a_0a0​的因子，bib_ibi​为ana_nan​的因子。

两两枚举因子，判断是否合法就行，注意还要枚举负因子。

注意，如果a0=0a_0=0a0​=0那么还有一个解为x=0x=0x=0，由于系数可能为000，所以我们需要人为的把系数不为000的最低次项作为方程的首项，最高次项作为方程的末项，再用上面的枚举因子的方法做。

转载于:.html