思路

把满足条件的数看成四个集合的并集：

• $A={k\in[1,n]\mid x\mid k}$（$x$ 的倍数）；
• $B={k\in[1,n]\mid y\mid k}$（$y$ 的倍数）；
• $C={k\in[1,n]\mid k\mid x}$（$x$ 的因子）；
• $D={k\in[1,n]\mid k\mid y}$（$y$ 的因子）。

直接对 $A\cup B\cup C\cup D$ 做四集合容斥代价较高，但注意：

本题为2025年8月23日美团机考原题

美团机考的介绍点击这里

题目内容

给你两个正整数 $x,y$ ，定义一个整数如果是特别的数，那么它一定满足以下条件至少其一：

• 它是 $x$ 的整数倍。

• 它是 $y$ 的整数倍。

• 它是 $x$ 的因子。

• 它是 $y$ 的因子。

给你一个整数 $n$ 请你求出 $1$ ~ $n$ 中有多少个整数是特别的数。

输入描述

输入一行三个整数 $n,x,y(1 ≦n,x,y ≦10^9)$ 如题意描述。

输出描述

输出一个整数表示 $1$ ~ $n$ 中特别的数的个数。

样例1

输入

10 3 5

输出

6