uva 10375(リロード演算子)
标题:既知C(m,n)=m!/(n!*(m-n!)),整数p,q,r,s(p>=q,r>=s,p,q,r,s<=10000)を入力し、C(p,q)/C(r,s)を計算します.出力保証は10^8を超えず、5桁の小数を保持する
#include
#include
#include
#include
#define f(i,l,r) for(i=(l);i<=(r);i++)
using namespace std;
const int MAXN=2000,MAXM=10000;
int p,q,r,s;
int Prime[MAXN],inp[MAXM+5];
struct bign{
int w[MAXN],pos=0;
bign(){
memset(w,0,sizeof(w));
pos=0;
}
bign(int x){
int i;
memset(w,0,sizeof(w));
if(x==0) return;
f(i,1,Prime[0]){
while(x%Prime[i]==0){
x/=Prime[i];
w[i]++;
}
if(x==1){
pos=i;
break;
}
}
}
bign operator * (const bign &x){
int i;
bign ans;
ans.pos=max(pos,x.pos);
f(i,1,ans.pos){
ans.w[i]=w[i]+x.w[i];
}
return ans;
}
bign operator / (const bign &x){
int i;
bign ans;
ans.pos=max(pos,x.pos);
f(i,1,ans.pos){
ans.w[i]=w[i]-x.w[i];
}
return ans;
}
};
bign Ans;
void Init()
{
int i,j;
f(i,2,MAXM){
if(!inp[i]){
Prime[++Prime[0]]=i;
}
f(j,1,Prime[0]){
if(i*Prime[j]>MAXM) continue;
inp[i*Prime[j]]=1;
if(i%Prime[j]==0) break;
}
}
}
void Multi(int a,int flag)
{
int i;
f(i,2,a){
bign tmp;
tmp=bign(i);
if(flag==1) Ans=Ans*tmp;
else Ans=Ans/tmp;
}
}
int main()
{
int i;
double ans;
Init();
while(cin>>p>>q>>r>>s){
Ans=bign(0);
ans=1;
Multi(p,1);
Multi(s,1);
Multi(r-s,1);
Multi(q,-1);
Multi(p-q,-1);
Multi(r,-1);
f(i,1,Ans.pos){
ans*=pow(Prime[i],Ans.w[i]);
}
cout<