1449: 七曜的考试

在一次离散数学的考试里面，七曜遇到了这样一道题目：对于 $1 - n$ 以内所有的整数 $i$ ，计算与整数 $x(\frac{i}{a+1}< x < \frac{i}{a})$满足$gcd(i, x) = 1$的数的个数.
$gcd(i, x)$ 代表 $i$ 与 $x$ 的最大公约数。

例如 $n = 3， a = 1$。  
$i = 1$时， $x$ 的范围为$(\frac{1}{2},1)$，不存在满足条件的$x$;  
$i = 2$时， $x$ 的范围为$(1,2)$，也不存在满足条件的 $x$ ;  
$i = 3$ 时， $x$ 的范围为$(\frac{3}{2}, 3)$，当$x=2$时，满足$gcd(2,3)=1$;  
故答案为$1$.

七曜不会这道题，但是七曜也不想挂科，所以请聪明的你帮七曜解决这个问题.

一行，两个整数 $n$ 和 $a$。意义见上文。  

数据范围：  
对于$20\%$ 的数据满足: $3 \leq n \leq 100,1 \leq a \leq 100,a + 1 < n$。  
对于$50\%$ 的数据满足: $3 \leq n \leq 2000,1 \leq a \leq 100,a + 1 < n$。  
对于$70\%$ 的数据满足: $3 \leq n \leq 10^4,1 \leq a \leq 100,a + 1 < n$。 
对于$100\%$ 的数据满足: $3 \leq n \leq2 \times 10^6,1 \leq a \leq 100,a + 1 < n$。

8 2

3

样例中
$i = 5$时,在范围 $(\frac{5}{3} - \frac{5}{2})$ $(1.6666... - 2.5)$内有整数 $2$，$2$与$5$互质.

$i = 7$时,在范围 $(\frac{7}{3} - \frac{7}{2})$$(2.3333... - 3.5)$内有整数 $3$，$3$与$7$互质.

$i = 8$时,在范围 $(\frac{8}{3} - \frac{8}{2})$ $(2.666... - 4)$内有整数 $3$，$3$与$8$互质.

所以答案是$3$.