首页 > 代码库 > UVA 10375 Choose and divide
UVA 10375 Choose and divide
n! 分解素因子 快速幂
ei=[N/pi^1]+ [N/pi^2]+ …… + [N/pi^n] 其中[]为取整
ei 为数 N!中pi 因子的个数;
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 8 const int maxn=10005; 9 10 int sign[maxn];11 int pri[maxn];12 int tot;13 14 void getpri (){15 memset (sign,0,sizeof sign);16 sign[0]=sign[1]=1;17 for (int i=2;i<sqrt (maxn+0.5);i++)18 if (!sign[i])19 for (int j=i*i;j<maxn;j+=i)20 sign[j]=1;21 tot=0;22 for (int i=2;i<maxn;i++)23 if (!sign[i])24 pri[tot++]=i;25 }26 27 int e[maxn];28 29 int power (int a,int b){30 int ans=1;31 while (b){32 if (b&1)33 ans*=a;34 a*=a;35 b>>=1;36 }37 return ans;38 }39 40 int main (){41 getpri ();//cout<<tot<<endl;42 int p,q,r,s;43 while (~scanf ("%d%d%d%d",&p,&q,&r,&s)/*cin>>p>>q>>r>>s*/){44 memset (e,0,sizeof e);45 int ma=max (p,r);46 for (int i=0;i<tot;i++){47 int temp=pri[i];48 while (temp<=ma){49 e[i]+=p/temp+s/temp+(r-s)/temp;//if (i==0) cout<<ma<<" ";50 e[i]-=r/temp+q/temp+(p-q)/temp;51 temp*=pri[i];52 }53 }54 double ans=1;55 for (int i=0;i<tot;i++){56 if (e[i]>=0)57 ans*=1.0*power (pri[i],e[i]);58 else ans/=1.0*power (pri[i],-e[i]);//cout<<e[i]<<":"<<pri[i]<<"=";//<<ans<<" ";59 }60 printf ("%.5f\n",ans);61 }62 return 0;63 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。