UOJ Logo Universal Online Judge

UOJ

#426. 【集训队作业2018】石像

统计

复活节岛上有 $n$ 个石像,每个石像的高度是一个 $[1,m]$ 之间的整数。设第 $i$ 个石像的高度为 $a_i$。

实际上,还有很多个像复活节岛一样的岛屿,一共有 $m^n$ 个(包括复活节岛),每个岛上都有 $n$ 个石像。由于某些原因,每个岛屿(包括复活节岛)都是独一无二的,即没有两个岛屿上的石像的高度是完全相同的。

每个岛上都聚集着很多能量,准确来说,有 $(\sigma_0(\gcd(a_1,a_2,\ldots,a_n)^3))^3$ 点能量。其中 $\sigma_0(n)$ 表示 $n$ 的因子个数。

几百年前,黑恶势力登陆地球,诅咒了所有岛屿:一共有 $k$ 个诅咒。第 $i$ 个诅咒可以用两个整数 $x_i,y_i$ 来表示,表示第 $x_i$ 个石像的高度不能超过第 $y_i$ 个石像的高度,即 $a_{x_i}\leq a_{y_i}$。如果一个岛上的石像的高度满足所有诅咒的要求,那么就不会发生任何事,否则整个岛屿就会被毁灭。所有岛上的诅咒都是相同的。

有些岛屿因此消失了,剩下的岛屿上的人把能量汇集在一起,击败了黑恶势力。

作为一名考古学家,你想知道剩下的岛屿的能量值的和是多少。

答案可能会很大,所以你只需要求出答案模 $2^{32}$ 的值。

一句话题意:求 $$ \left(\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_n=1}^m{\left(\sigma_0\left(\gcd\left(a_1,a_2,\ldots,a_n\right)^3\right)\right)}^3\prod_{i=1}^k\left[a_{x_i}\leq a_{y_i}\right]\right)\bmod 2^{32} $$

输入格式

第一行有三个整数 $n,m,k$。

接下来 $k$ 行每行有两个整数:第 $i$ 行的两个整数为 $x_i,y_i$。

输出格式

一个整数:答案。

样例一

input

2 2 1
1 2

output

66

explanation

总共有三种不同的情况:

  • $a_1=1,a_2=1,s=1,\sigma_0(s^3)^3=1$。
  • $a_1=1,a_2=2,s=1,\sigma_0(s^3)^3=1$。
  • $a_1=2,a_2=2,s=2,\sigma_0(s^3)^3=64$。

样例二

input

5 10 4
1 2
1 3
2 4
2 5

output

54283

限制与约定

子任务分值$n$$m$$k$
$1$$5$$\leq 5$$\leq 10$$\leq n(n-1)$
$2$$15$$\leq 13$$\leq 13$
$3$$30$$\leq 20$$\leq {10}^7$
$4$$30$$\leq {10}^{10}$$=0$
$5$$20$$\leq n(n-1)$

对于所有数据:$1\leq n\leq 20,1\leq m\leq {10}^{10},0\leq k\leq n(n-1)$,不存在两个相同的诅咒。

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

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

下载

样例数据下载