题目描述

某地发行一套彩票。彩票上写有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。

输入输出样例

输入样例#1：

2 4 3 4

输出样例#1：

1 搜索+疯剪(疯狂剪枝) 还要注意精度 剪枝：可行性剪枝 如果之后的几个最大倒数的和相加小于x/y 或最小倒数的和相加大于x/y就可以剪枝

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 using namespace std; 7 int ans,n,m; 8 double p,s[10001]; 9 void dfs(int cen,int x,double sum)10 {11   if (sum+s[x+n-cen]-s[x]-p<=-1e-10) return;12   if (sum+s[m]-s[m-n+cen]-p>=1e-10) return;13   if (cen>=n&&fabs(sum-p)<=1e-10)14     {15       ans++;16       return;17     }18     if (sum-p>=1e-10) return;19   if (cen>=n) return;20   dfs(cen,x+1,sum);21   dfs(cen+1,x+1,sum+(double)(1.0/(double)(x+1)));22 }23 int main()24 {
      int i;25   double x,y;26   cin>>n>>m>>x>>y;27   p=x/y;28   for (i=1;i<=m;i++)29     s[i]=s[i-1]+(1.0/(double)i);30   s[m+1]=s[m];31   dfs(0,0,0);32   cout<