#P4173. [2015年湖南省队省队集训]数学

    ID: 3388 传统题 1000ms 256MiB 尝试: 859 已通过: 279 难度: 6 上传者: 标签>CF2100提高向下取整与向上取整欧拉函数交换求和顺序等差数列求和试除法分解质因数

[2015年湖南省队省队集训]数学

题目描述

对正整数 n,mn,m,定义

$$S(n,m)=\{k\in\mathbb Z_{>0}\mid (m\bmod k)+(n\bmod k)\ge k\}.$$

例如,S(7,9)={2,4,5,8,10,11,12,13,14,15,16}S(7,9)=\{2,4,5,8,10,11,12,13,14,15,16\}。设 φ\varphi 为欧拉函数。求

$$\left(\varphi(n)\varphi(m)\sum_{k\in S(n,m)}\varphi(k)\right)\bmod 998244353.$$

输入格式

第一行两个正整数 n,mn,m。

输出格式

输出一行一个整数,表示所求结果。

样例

5 6
240

数据范围

  • 对于 20%20\% 的数据,n,m≤103n,m\le10^3。
  • 对于 40%40\% 的数据,n,m≤107n,m\le10^7。
  • 对于所有数据,n,m≤1015n,m\le10^{15}。

原 PDF 题面