Dotcpp  >  编程题库  >  蓝桥杯2023年第十四届省赛真题-互质数的个数
题目 3162:

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

时间限制: 2s 内存限制: 320MB 提交: 2956 解决: 295

题目描述

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

输入格式

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

输出格式

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

样例输入

2 5

样例输出

16

提示

对于 30% 的评测用例,ab ≤ 106
对于 70% 的评测用例,a ≤ 106,b ≤ 109
对于所有评测用例,1 ≤ a ≤ 109,1 ≤ b ≤ 1018
标签