#1925. 小 Bo 的数列

    ID: 1925 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1974来源:qoj.ac数据:公开样例数论

小 Bo 的数列

小 Bo 的数列

题目描述

标题: 小 Bo 的数列 - Problem - QOJ.ac

#10360. 小 Bo 的数列

Statistics

The problem was used in the following contests:

Warning: 附加文件中的 trans.cpp 不可用,因此本题暂时无法解决。

小 Bo 特别喜欢数列。有一天他偶尔得到了一个序列,这个序列是无限长的,但特殊的是这个序列中只有 N 个位置有值。 小 Bo 将这个序列存在了自己的笔记本中。不幸的是,有一天他忘记锁屏了。一个熊孩子看到了他的数列,决定做一些恶作剧。

熊孩子先将这个序列 A 复制到一个新的序列 B 里,然后做了 t 次操作,每次将 B 赋值为 A 与 B 的 狄里克雷卷积 结果。 最后,熊孩子又新建了一个序列 C,并将 B 中的第 i 项加到了 C 中的第 trans(i,M) 项,并输出了序列 C。

这时,小 Bo 突然回来了,熊孩子落荒而逃,匆忙之中落下了记录着 M 的纸片。小 Bo 发现桌面上多了一个根本打不开的文件。 通过各种渠道,小 Bo 又得到了 trans(i, M) 的具体代码。

现在小 Bo 想要知道这个序列 C 是什么样子的,但是 C 太长了,所以他只想知道 ∑i≥1Ci⋅i,请你帮助他得到这个结果。

在附件中给出了 trans.cpp,用来描述 trans 函数。

输入格式

第一行三个整数 N,m,t,分别描述序列中有值的位置数量、M 中不同质因子个数和操作次数。

接下来 m 行,每行两个正整数 pi,ci,其中 M=∏i=1mpici。

接下来 N 行,每行两个正整数 ai,bi,表示 Aai=bi。

输出格式

一行,输出答案模 1163962801 的值。

样例

样例输入一

3 1 1
3 1
2 5
5 3
6 1

样例输出一

729

样例说明

原序列 A 中,有 A2=5,A5=3,A6=1。

操作过后得到的序列 B 为 B4=25,B10=30,B12=10,B25=9,B30=6,B36=1。

M=3,M 中可用的约数仅有 3。

4,10,25 经过 trans 后数值不变,trans(12,M)=4,trans(30,M)=10,trans(36,M)=4。

于是最后的序列 C 为 C4=36,C10=36,C25=9。

答案为 36×4+36×10+9×25=729。

数据规模与约定

本题一共 10 个测试数据,每个测试数据的分值为 10 分。

每个数据的特殊性质请参见下表:

ID N m t 特殊约定 1 5 / ≤3 M≤20,ai≤M 2 ≤1000 / ≤1000 M≤109, ai 是 M 的约数 3 ≤1000 / / M≤109, ai 是 M 的约数 4 / ≤200 / ai 是 M 的约数 5 / / / ai 是 M 的约数 6 / ≤200 / ci≤2 7 / / / ci≤2 8 / ≤200 / / 9 / / / / 10 / / / /

保证 100% 的数据满足:

  • 1≤N,m≤100000
  • 0≤t≤109
  • 1≤ai,bi≤109
  • 2≤pi≤109,数据保证 pi,ai 互不相同,且 pi 是质数
  • 1≤ci≤20,∏i=1mci≤105

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 1 1
3 1
2 5
5 3
6 1
729