#1948. 石像

石像

石像

题目描述

标题: 石像 - Problem - QOJ.ac

#13626. 石像

Statistics

The problem was used in the following contests:

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

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

每个岛上都聚集着很多能量,准确来说,有 (σ0(gcd(a1,a2,…,an)3))3 点能量。其中 σ0(n) 表示 n 的因子个数。

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

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

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

答案可能会很大,所以你只需要求出答案模 232 的值。

一句话题意:求 (m∑a1=1m∑a2=1⋯m∑an=1(σ0(gcd(a1,a2,…,an)3))3k∏i=1[axi≤ayi])mod232

输入格式

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

接下来 k 行每行有两个整数:第 i 行的两个整数为 xi,yi。

输出格式

一个整数:答案。

样例一

input

2 2 1
1 2

output

66

explanation

总共有三种不同的情况:

  • a1=1,a2=1,s=1,σ0(s3)3=1。
  • a1=1,a2=2,s=1,σ0(s3)3=1。
  • a1=2,a2=2,s=2,σ0(s3)3=64。

样例二

input

5 10 4
1 2
1 3
2 4
2 5

output

54283

限制与约定

子任务分值nmk 15≤5≤10≤n(n−1) 215≤13≤13 330≤20≤107 430≤1010=0 520≤n(n−1)

对于所有数据:1≤n≤20,1≤m≤1010,0≤k≤n(n−1),不存在两个相同的诅咒。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 2 1
1 2
66

样例 2

5 10 4
1 2
1 3
2 4
2 5
54283