#P2236. [HNOI2002] 彩票

    ID: 1252 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>各省省选湖南2002概率论统计Splay深度优先搜索DFS

[HNOI2002] 彩票

题目描述

某地发行一套彩票。彩票上写有 11MMMM 个自然数。彩民可以在这 MM 个数中任意选取 NN 个不同的数打圈。每个彩民只能买一张彩票,不同的彩民的彩票上的选择不同。

每次抽奖将抽出两个自然数 XXYY。如果某人拿到的彩票上,所选 NN 个自然数的倒数和,恰好等于 XY\dfrac{X}{Y},则他将获得一个纪念品。

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

输入格式

输入文件有且仅有一行,就是用空格分开的四个整数 NNMMXXYY

输出格式

输出文件有且仅有一行,即所需准备的纪念品数量。

2 4 3 4
1

提示

1X,Y1001 \leq X, Y \leq 1001N101 \leq N \leq 101M501 \leq M \leq 50

输入数据保证输出结果不超过 10510^5