蓝桥杯2023年第十四届省赛真题-互质数的个数

提交: 3042 解决: 311

题目描述

给定 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¹⁸ 。

标签

上一题下一题