某地发行一套彩票。彩票上写有1到M这M个自然数。彩民可以在这M个数中任意选取N个不同的数打圈。每个彩民只能买一张彩票，不同的彩民的彩票上的选择不同。

每次抽奖将抽出两个自然数X和Y。如果某人拿到的彩票上，所选N个自然数的倒数和，恰好等于X/Y，则他将获得一个纪念品。

已知抽奖结果X和Y。现在的问题是，必须准备多少纪念品，才能保证支付所有获奖者的奖品。

输入文件有且仅有一行，就是用空格分开的四个整数N，M，X，Y。

输出文件有且仅有一行，即所需准备的纪念品数量。 1≤X, Y≤100，1≤N≤10，1≤M≤50。输入数据保证输出结果不超过10^5。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<string>

  using namespace std;

 const double MINN=1e-;//浮点数计算有误差

 int x,y,n,m;

 double ans;

 double pre[];//预处理，前缀和

 int cnt;

 void dfs(int cen,int first,double tol)//当前第cen层，从first开始循环，当前总和为tol

 {

     double minn=tol+pre[m]-pre[m-(n-cen)];//tol加上未计算最小的和

     double maxn=tol+pre[first+(n-cen)]-pre[first];//tol加上未计算最大的和

     if (minn-ans>MINN||maxn-ans<-MINN) return;//判断过多或过少的条件

     if (cen>=n)

     {

         cnt++;

         return;

     }

     if (cen>=n) return;

     dfs(cen,first+,tol);

     dfs(cen+,first+,tol+1.0/(first+));//考虑当前选与不选

     return;

 }

 int main()

 {

     scanf("%d%d%d%d",&n,&m,&x,&y);

     ans=(double)x/(double)y;

     for (int i=;i<=m;i++)

         pre[i]=pre[i-]+1.0/(double)(i);

     dfs(,,);

     printf("%d\n",cnt);

     return ;

 }