2023蓝桥杯国赛一模_问题B

提交: 3057 解决: 312

题目描述

给定 a, b，求 1 ≤ x < a^b 中有多少个 x 与 a^b 互质。由于答案可能很大，你只需要输出答案对 998244353 取模的结果。

输入

输入一行包含两个整数分别表示 a, b，用一个空格分隔。

输出

输出一行包含一个整数表示答案。

样例输入

2 5

样例输出

提示

对于 30% 的评测用例，a^b ≤ 10⁶ ；

对于 70% 的评测用例，a ≤ 10⁶，b ≤ 10⁹ ；

对于所有评测用例，1 ≤ a ≤ 10⁹，1 ≤ b ≤ 10¹⁸ 。

加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油