注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

CTSC2013 因式分解 闲扯  

2014-03-15 22:05:01|  分类: ctsc |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
双倍经验题
http://www.lydsy.com/JudgeOnline/problem.php?id=2742
用的是杜教的做法……同时也是这题的做法
枚举约数,选70个质数,在模意义下验根以及做多项式除单项式的操作
读入输出有点蛋疼……这让我想起了普及组的多项式输出
质数表复制粘贴的vfleaking的

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<cctype>
#define each(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
#define maxn 100
#define MOD 1000000000
using namespace std;
typedef long long LL;
const int nPrime = 70;
const int Prime[nPrime] =
{
1000000007,
1000000009,
1000000021,
1000000033,
1000000087,
1000000093,
1000000097,
1000000103,
1000000123,
1000000181,
1000000207,
1000000223,
1000000241,
1000000271,
1000000289,
1000000297,
1000000321,
1000000349,
1000000363,
1000000403,
1000000409,
1000000411,
1000000427,
1000000433,
1000000439,
1000000447,
1000000453,
1000000459,
1000000483,
1000000513,
1000000531,
1000000579,
1000000607,
1000000613,
1000000637,
1000000663,
1000000711,
1000000753,
1000000787,
1000000801,
1000000829,
1000000861,
1000000871,
1000000891,
1000000901,
1000000919,
1000000931,
1000000933,
1000000993,
1000001011,
1000001021,
1000001053,
1000001087,
1000001099,
1000001137,
1000001161,
1000001203,
1000001213,
1000001237,
1000001263,
1000001269,
1000001273,
1000001279,
1000001311,
1000001329,
1000001333,
1000001351,
1000001371,
1000001393,
1000001413
};
struct frac
{
LL fenzi,fenmu;
frac() {}
frac(LL fenzi,LL fenmu): fenzi(fenzi),fenmu(fenmu) {}
friend bool operator < (const frac &a,const frac &b)
{
return a.fenzi*b.fenmu>b.fenzi*a.fenmu;
}
};
struct Node
{
frac p;
int n;
Node() {}
Node(frac p,int n): p(p),n(n) {}
friend bool operator < (const Node &a,const Node &b)
{
return a.p<b.p;
}
};
vector<Node> sol;
struct bign
{
int digit[40],n,sign;
void get(char *str,int sig,int len)
{
sign=sig;
for(int i=len;i>=1;i-=9)
{
++n;
for(int j=max(1,i-8);j<=i;++j)
digit[n]=digit[n]*10+str[j]-'0';
}
}
void print()
{
printf("%d",digit[n]);
for(int i=n-1;i>=1;--i)
printf("%09d",digit[i]);
}
int operator % (int p)
{
LL rem=0;
for(int i=n;i>=1;--i)
rem=(rem*MOD+digit[i])%p;
return rem;
}
}a[maxn];
LL A[80][maxn];
int n;
void read()
{
string s1,s2;
cin>>s1;
for(int i=0;i<(int)s1.length();++i)
{
if(s1[i]=='+'||s1[i]=='-')
s2+="#",s2+=s1[i];
else
s2+=s1[i];
}
static char str[350];
char c;
for(int i=0;i<(int)s2.length();)
{
int tot=0,sign=1;
for(c=s2[i++];!isdigit(c)&&c!='-'&&c!='x';c=s2[i++]);
if(c=='-')
sign=-1,c=s2[i++];
if(c=='x')
{
str[++tot]='1';
c=s2[i++];
if(c=='^')
{
int num=0;
for(c=s2[i++];isdigit(c);c=s2[i++])
num=num*10+c-'0';
n=max(n,num);
a[num].get(str,sign,tot);
}
else
a[1].get(str,sign,tot);
continue;
}
else
{
str[++tot]=c;
for(c=s2[i++];isdigit(c);c=s2[i++])
str[++tot]=c;
}
if(c==0)
a[0].get(str,sign,tot);
else
{
c=s2[i++];
if(c!='^')
a[1].get(str,sign,tot);
else
{
c=s2[i++];
int num=0;
for(;isdigit(c);c=s2[i++])
num=num*10+c-'0';
a[num].get(str,sign,tot);
n=max(n,num);
}
}
}
if(a[n].sign<0)
printf("-");
if(a[n].n!=1||a[n].digit[1]!=1)
a[n].print();
}
LL power(LL p,int n,int mod)
{
LL ans=1;
for(;n;n>>=1,p=p*p%mod)
if(n&1)
ans=ans*p%mod;
return ans;
}
void Div(int num,LL p,LL q)
{
int mod=Prime[num];
if(p<0)
p=(mod+p)%mod;
p=p*power(q,mod-2,mod)%mod;
for(int i=n;i>=0;--i)
A[num][i]=(A[num][i]+A[num][i+1]*p)%mod;
}
bool check(int num,LL p,LL q)
{
int mod=Prime[num];
if(p<0)
p=(mod+p)%mod;
p=p*power(q,mod-2,mod)%mod;
LL sum=0;
for(int i=n;i>=0;--i)
sum=(sum*p+A[num][i])%mod;
return sum==0;
}
bool check(int p,int q)
{
for(int i=0;i<nPrime;++i)
if(check(i,p,q)==false)
return false;
return true;
}
void work()
{
Node o=Node(frac(0,1),0);
int st;
for(st=0;a[st].n==0;++st)
++o.n;
for(int i=st;i<=n;++i)
a[i-st]=a[i];
n-=st;
for(int i=0;i<nPrime;++i)
for(int j=0;j<=n;++j)
{
A[i][j]=a[j]%Prime[i];
if(a[j].sign<0)
A[i][j]=(Prime[i]-A[i][j])%Prime[i];
}
if(o.n)
sol.push_back(o);
static int d1[100000],d2[100000];
int n1=0,n2=0;
for(int i=1;i<=1000000;++i)
{
if(a[0]%i==0)
d1[++n1]=i;
if(a[n]%i==0)
d2[++n2]=i;
}
for(int i=1;i<=n1;++i)
for(int j=1;j<=n2;++j)
if(__gcd(d1[i],d2[j]))
{
o=Node(frac(d1[i],d2[j]),0);
while(check(d1[i],d2[j]))
{
++o.n;
for(int k=0;k<nPrime;++k)
Div(k,d1[i],d2[j]);
}
if(o.n)
sol.push_back(o);
o=Node(frac(-d1[i],d2[j]),0);
while(check(-d1[i],d2[j]))
{
++o.n;
for(int k=0;k<nPrime;++k)
Div(k,-d1[i],d2[j]);
}
if(o.n)
sol.push_back(o);
}
}
void print()
{
sort(sol.begin(),sol.end());
each(i,sol)
{
if(i->p.fenzi==0)
printf("x");
else
{
if(i->p.fenmu==1)
{
if(i->p.fenzi<0)
printf("(x+%lld)",-i->p.fenzi);
else
printf("(x%lld)",-i->p.fenzi);
}
else
{
if(i->p.fenzi<0)
printf("(x+%lld/%lld)",-i->p.fenzi,i->p.fenmu);
else
printf("(x%lld/%lld)",-i->p.fenzi,i->p.fenmu);
}
if(i->n>1)
printf("^%d",i->n);
}
}
printf("\n");
}
int main()
{
read();
work();
print();
return 0;
}

  评论这张
 
阅读(2193)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017