Problem1341--PIPI学容斥

1341: PIPI学容斥

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 715  Solved: 321
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI最近学了容斥原理:
两个集合的容斥关系公式: |A∪B| = |A|+|B| - |A∩B |(∩：重合的部分）
三个集合的容斥关系公式：|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C|
...
现在PIPI想用容斥原理来解决一个简单的问题:
给定正整数 n , a, b, c 。让你求出1~n中能够被 a或 b或 c整除的数的个数。

Input

输入包含多组数据。
每一组数据包含三个数字 n , a , b , c 。(1<=a, b, c, n <=1e9)。

Output

对于每一组测试用例，输出1~n中能够被a 或者 b 或者 c整除的数的个数。

Sample Input 

1000 2 3 5
100 2 3 5

Sample Output 

734
74

Source/Category

中等 数学 
[Submit] [Status]