U330353 互质

给定两个正整数 $n$ 和 $m$，表示问在区间 $[1,n]$ 中有多少个数与 $m$ 互质。 ps：我们称 $a$ 与 $b$ 互质当且仅当 $\gcd(a,b)=1$，其中 $\gcd$ 表示最大公因数。

一行两个数，表示 $n$ 和 $m$。

一行一个数，表示答案。

样例解释#1： 在区间 $[1,5]$ 中，除 $5$ 外均与 $5$ 互质。 样例解释#2： 在区间 $[1,6]$ 中，$1$、$5$ 与 $6$ 互质。 --- 本题共有 $15$ 个测试点，测试点不同分，本题不捆绑。 | 测试点 | $n$ | $m$ | 特殊性质 | 总分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\le 10^{18}$ | $\le 10^{12}$ | A | $4$ | | $2-3$ | $\le 10^6$ | $\le 10^{12}$ | | $12$ | | $4-6$ | $\le 10^{18}$ | $=8$ | | $12$ | | $7-9$ | $\le 10^{18}$ | $=30$ | | $18$ | | $10-15$ | $\le 10^{18}$ | $\le 10^{12}$ | | $54$ | 特殊性质 A：保证 $m$ 为质数。 对于 $100\%$ 的数据，$1 \le n \le 10^{18}$，$1 \le m \le 10^{12}$。