QOJ.ac

QOJ

Time Limit: 25 s Memory Limit: 2048 MB

# 8327. 积性函数求和 $10^{13}$ 方便 FFT 版

统计

很久以前的某一天,你发现了一个神奇的函数 $f(x)$,它满足很多神奇的性质:

  1. $f(1)=1$。
  2. $f(p^e)= ae + bp$($p$ 为质数)。
  3. $f(xy)=f(x)f(y)$($x$ 与 $y$ 互质)。

令 $S(m)=\sum\limits_{i=1}^m f(i) \bmod 469762049$,你需要对于 $i=1,2,3,\cdots,n$ 求出 $S(\lfloor n/i\rfloor)$,去重并输出异或和。

注:为鼓励探索新做法,本题使用了精心挑选的数 $469762049$。域 $\mathbb{Z} / 469762049 \mathbb{Z}$ 有 $2^{26}$ 次本原单位根,$3$ 是它的一个原根。

输入格式

第一行一个正整数 $T$,表示有 $T$ 组测试数据。

接下来 $T$ 行,第 $i$ 行 $3$ 个正整数 $n_i$,$a_i$,$b_i$,其中 $a_i$ 和 $b_i$ 为 $f(x)$ 的性质 2 中的参数 $a$ 和 $b$。

输出格式

输出 $T$ 行,第 $i$ 行一个非负整数,表示去重后的 $\left\{S(\lfloor n/i\rfloor)\right\}_{i\in[1,n_i]}$ 的异或和。

样例数据

样例 1 输入

1
6 2 2

样例 1 输出

90

样例 1 解释

去重后的集合为 $\{1, 7, 15, 83\}$,异或和为 $90$。

样例 2 输入

1
233333 29 31

样例 2 输出

227062462

样例 3 输入

1
9876543210 98765 43210

样例 3 输出

78615365

子任务

$1 \leq T \leq 10^4$。

$0 \leq a_i, b_i < 469762049$。

当 $T = 1$ 时,$1 \leq n \leq 10^{13}$,否则 $1 \leq T \sqrt{\max_{i=1}^T n_i} \leq 10^6$