#6686. Stupid GCD

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: siyuan

题目描述

本题为 HDU 6588 加强版。

给定正整数 n ,请你求出如下式子的值:

\sum_{i = 1} ^ {n} \gcd\left(\left\lfloor\sqrt[3]{i}\right\rfloor, i\right)

答案对 998244353 取模。

输入格式

1 行。

1 行:一个正整数 n

输出格式

1 行。

1 行:一个整数表示上述式子对 998244353 取模的值。

样例

样例输入 1

987654

样例输出 1

3595606

样例输入 2

98723489637846786423

样例输出 2

765547726

数据范围与提示

本题采用捆绑测试。

子任务编号 分值 n
1 20 \le 10 ^ {6}
2 \le 10 ^ {18}
3 30 \le 10 ^ {21}
4 \le 10 ^ {30}

考虑到 n 的范围超过 long long,因此变量类型需要采用 __int128(其范围是 [-2 ^ {127}, 2 ^ {127}) )。而 C++ 内并没有兼容 __int128 的输入方式。下面给出用于输入 __int128 的函数:

template <class Tp>
void read(Tp &x) {
	static char ch;
	static bool neg;
	for (ch = neg = 0; ch < '0' || ch > '9'; neg |= (ch == '-'), ch = getchar());
	for (x = 0; ch >= '0' && ch <= '9'; (x *= 10) += (ch ^ 48), ch = getchar());
	neg && (x = -x);
}