4744 互质的个数
时间限制1 S
内存限制128 MB
通过率15.4%(16 / 104)
题目描述
给定 a, b，求 1 ≤ x < ab 中有多少个 x 与 ab 互质。
由于答案可能很大，你只需要输出答案对 998244353 取模的结果。
由于答案可能很大，你只需要输出答案对 998244353 取模的结果。
输入格式
输入一行包含两个整数分别表示 a, b，用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
输入输出样例
输入复制
2 5输出复制
16数据范围与提示
对于 30% 的评测用例，ab ≤ 106；
对于 70% 的评测用例，a ≤ 106，b ≤ 109；
对于所有评测用例，1 ≤ a ≤ 109，1 ≤ b ≤ 1018。
对于 70% 的评测用例，a ≤ 106，b ≤ 109；
对于所有评测用例，1 ≤ a ≤ 109，1 ≤ b ≤ 1018。
来源