破解谜匣

三层加密都过了——光点、余波、间隙、高塔——但Zero的核心还没有打开。最后一道锁，是一个谜匣。

"谜匣？"CC问。

"对。"Echo说，"一个盒子，里面有很多格子。每个格子里有一个数。我们要找出所有满足条件的格子——它们的数的乘积等于一个给定的值。"

"啥条件？"

"给定$n$和$m$。"你说，"求$1$到$n$中，所有满足$\gcd(i,n)=m$的$i$的个数。"

"gcd是啥？"

"最大公约数。"你说，"两个数共同拥有的最大约数。"

"这咋算？"

"先除。"你说，"如果$\gcd(i,n)=m$，那么$m$必须整除$n$。设$n'=n/m$，$i'=i/m$，则$\gcd(i',n')=1$。"

"然后呢？"

"然后问题变成：求$1$到$n'$中与$n'$互质的数的个数——这就是欧拉函数$\varphi(n')$。"

"欧拉函数？"

"对。"你说，"$\varphi(n)$表示$1$到$n$中与$n$互质的数的个数。"

"咋算？"

"先质因数分解。"你说，"$\varphi(n)=n\times\prod_{p|n}(1-1/p)$。"

你开始算。$n$的质因数分解，然后套公式。

"第47个谜匣。"你说，"$n=47$，$m=1$——答案是46。"

"46？"

"对。"你说，"47是质数，所以除了47自己，其他46个数都和47互质。"

"简单。"

"对。"你说，"有时候，简单就是答案。"

CC把46刻在手臂最后一个空位上——45360，12，19，46。

"满了。"她说。

"满了。"你说。

"那我开始背。"CC说，"45360，12，19，46。"

"背这个干啥？"

"密码。"她说，"开门的密码。"

Echo看着CC背数字的样子——像念经，像祈祷，像某种古老的仪式。

"以前Echo-0也背过。"她说。

"背啥？"

"47。"她说，"只有47。"

"现在多了。"你说。

"对。"Echo说，"现在多了。"

题目描述

给定$n$和$m$，求$1$到$n$中满足$\gcd(i,n)=m$的正整数$i$的个数。

输入格式

两个整数$n$和$m$。

输出格式

满足条件的整数个数。

输入样例

5

输出样例

0

提示

• 若$\gcd(i,n)=m$，则$m|n$。设$n'=n/m$，$i'=i/m$，则$\gcd(i',n')=1$。
• 答案为欧拉函数$\varphi(n')$。
• $n'\le 10^7$，线性筛预处理欧拉函数。