首页 > 代码库 > 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 }