UOJ Logo Universal Online Judge

UOJ

#578. 【ULR #1】校验码

附件下载 统计

“跳找”搜索引擎的开发过程涉及到大量数据包的传输,为了保证传输过程稳定,你选择了用下面的方式算出一个校验码:

定义函数 $q(n,c)$ ,满足下列性质:

  • 对所有质数 $p$ 和非负整数 $k$,有 $q\left(p^k,c\right)=p^{c\lfloor k/2\rfloor}\,$;

  • 对所有互质的正整数 $n,m$ 有 $q(nm,c)=q(n,c)q(m,c)$。(即在第一维上满足积性)

不难发现,当 $c$ 确定后,可以根据上述性质唯一确定每个 $q(n,c)$ 的值。

我们可以把数据包认为是由若干个非负整数对 $(u_i,v_i)$ 组成的序列。这样我们先通过上面的算法计算出 $q(u_i\cdot v_i,c)$ 作为该整数对的校验码,然后将所有整数对的校验码求和再对 $2^{32}$ 取余后,就可以得到数据包的校验和。

现在你有一个非常大的数据包,其大小为 $n\times m$,且对于所有满足 $1 \le i \le n,1 \le j \le m$ 的 $(i,j)$,数据包中包含恰好一个整数对 $(i,j)$。请你计算出该数据包的校验和。

也就是说,对于给定的正整数 $n,m,c$,你需要求出下列式子对 $2^{32}$ 取模的值:

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^mq(ij,c).$$

输入格式

本题有多组测试数据。

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

下面 $T$ 行,每行三个整数 : $n,m,c$,意义如题目所述。

输出格式

对于每组测试数据,输出一行一个整数,表示答案对 $2^{32}$ 取模的结果。

样例一

input

3
10 100 1
998 244 353
1911 1949 1978

output

3733
3704996707
981669122

样例二

input

3
1 9078917 1
1 99989717 22
92734 3529465017 68175

output

49378630
1117102208
1722526387

限制与约定

对于所有数据, $1\leq n\leq 5\times 10^5,\ 1\leq m \leq 1.2\times 10^{11}\ ,1\leq c\leq 10^5 ,1\leq T\leq 3$。

子任务编号 $n\leq$ $m\leq $ 分值
$1$ $2000$ $2000$ $10$
$2$ $5\times10^5$ $5\times10^5$ $15$
$3$ $1$ $5\times 10^{9}$ $15$
$4$ $1.2\times 10^{11}$ $10$
$5$ $10^4$ $10^9$ $15$
$6$ $10^5$ $10^{10}$ $15$
$7$ $5\times 10^5$ $1.2\times 10^{11}$ $20$

时间限制:$5\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载