题解 P4506 【[CTSC2013]因式分解】
违规用户名142305 · · 题解
假设分解为∏(pix+qi)，那么就有∏pi=An，∏qi=A0。由于有pi<=1000000，qi<=1000000，我们枚举An和A0的约数然后暴力枚举判断。。。
至于于是判断，可以考虑在模意义下判断，选70个大质数分别判断即可。。。
剩下的就是码码码了。。
AC代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int prm[70]={543892411,567498259,643448581,772660877,802279559,823153213,847485637,907170331,919507003,923425961,929812711,935151689,938910911,962946403,970870897,977946113,985116131,989743967,991308817,994793521,995403061,997310857,998623607,999049111,999860857,1000885111,1002002609,1002270383,1002326077,1002351107,1002642457,1002681557,1003013519,1004475841,1005879367,1006478441,1007120461,1007468677,1007576071,1008054149,1008640013,1008894637,1009316083,1009528721,1009862393,1010510329,1010915173,1011460739,1012072651,1012612079,1012668131,1012825181,1014091867,1014515053,1014904973,1015114333,1015944323,1016003431,1016121461,1017088367,1017307463,1017423811,1017620873,1018394743,1018932493,1019199101,1019208581,1019319187,1019376101,1019831203};
int n,m,cnt,tot1,tot2,b[70][85],p[100005],q[100005];
char s0[30005],s1[30005];
struct node{ int x,y,z; }ans[85];
bool cmp(const node &u,const node &v){
return (ll)u.x*v.y>(ll)u.y*v.x;
}
struct hugnum{
int len,sgn,num[40];
void ins(int tot,int fu){
int i,j; sgn=fu;
for (i=tot; i>0; i-=9){
len++;
for (j=max(1,i-8); j<=i; j++) num[len]=num[len]*10+s1[j]-'0';
}
}
int getmod(int x){
int i,t=0;
for (i=len; i; i--)
t=((ll)t*1000000000+num[i])%x;
return t;
}
}a[85];
void get_in(){
scanf("%s",s0+1);
int i=1,len=strlen(s0+1);
while (i<=len){
int tot=0,fu=1,dgr=0;
if (s0[i]=='-') fu=-1;
if (s0[i]=='+' || s0[i]=='-') i++;
if (s0[i]=='x'){
s1[tot=1]='1'; i++;
if (s0[i]=='^'){
for (i++; s0[i]>='0' && s0[i]<='9'; i++)
dgr=dgr*10+s0[i]-'0';
a[dgr].ins(tot,fu);
if (!n) n=dgr;
} else a[1].ins(tot,fu);
} else{
for (; s0[i]>='0' && s0[i]<='9'; i++) s1[++tot]=s0[i];
if (!s0[i]) a[0].ins(tot,fu); else{
i++;
if (s0[i]=='^'){
for (i++; s0[i]>='0' && s0[i]<='9'; i++)
dgr=dgr*10+s0[i]-'0';
a[dgr].ins(tot,fu);
if (!n) n=dgr;
} else a[1].ins(tot,fu);
}
}
}
if (a[n].sgn<0) putchar('-');
if (a[n].len>1 || a[n].num[1]>1){
printf("%d",a[n].num[a[n].len]);
for (i=a[n].len-1; i; i--) printf("%09d",a[n].num[i]);
}
}
void put_out(){
sort(ans+1,ans+cnt+1,cmp); int i;
for (i=1; i<=cnt; i++){
if (!ans[i].x) putchar('x'); else
if (ans[i].y==1)
if (ans[i].x<0) printf("(x+%d)",-ans[i].x);
else printf("(x%d)",-ans[i].x);
else
if (ans[i].x<0) printf("(x+%d/%d)",-ans[i].x,ans[i].y);
else printf("(x%d/%d)",-ans[i].x,ans[i].y);
if (ans[i].z>1) printf("^%d",ans[i].z);
}
puts("");
}
int ksm(int x,int y,int mod){
int t=1; for (; y; y>>=1,x=(ll)x*x%mod) if (y&1) t=(ll)t*x%mod;
return t;
}
int gcd(int x,int y){ return (y)?gcd(y,x%y):x; }
bool ok(int x,int y){
int i,j,t,mod,tmp;
for (i=0; i<70; i++){
mod=prm[i]; t=(x+mod)%mod;
t=(ll)t*ksm(y,mod-2,mod)%mod;
for (j=n,tmp=0; j>=0; j--)
tmp=((ll)tmp*t+b[i][j])%mod;
if (tmp) return 0;
}
return 1;
}
void divide(int x,int y){
int i,j,t,mod;
for (i=0; i<70; i++){
mod=prm[i]; t=(x+mod)%mod;
t=(ll)t*ksm(y,mod-2,mod)%mod;
for (j=n; j>=0; j--)
b[i][j]=((ll)b[i][j+1]*t+b[i][j])%mod;
}
}
int main(){
get_in();
int i=0,j,k; while (!a[i].len) i++;
if (i>0) ans[++cnt]=(node){0,1,i};
for (j=i; j<=n; j++) a[j-i]=a[j];
n-=i;
for (i=0; i<70; i++)
for (j=0; j<=n; j++) b[i][j]=(a[j].getmod(prm[i])*a[j].sgn+prm[i])%prm[i];
for (i=1; i<=1000000; i++){
if (!a[0].getmod(i)) p[++tot1]=i;
if (!a[n].getmod(i)) q[++tot2]=i;
}
for (i=1; i<=tot1; i++)
for (j=1; j<=tot2; j++) if (gcd(p[i],q[j])==1){
for (k=0; ok(p[i],q[j]); k++)
divide(p[i],q[j]);
if (k) ans[++cnt]=(node){p[i],q[j],k};
for (k=0; ok(-p[i],q[j]); k++)
divide(-p[i],q[j]);
if (k) ans[++cnt]=(node){-p[i],q[j],k};
}
put_out();
return 0;
}