背景
板子。
题目描述
定义二维数论函数 f(x,y) 是积性函数,当且仅当对于所有 gcd(ab,cd)=1,都有 f(ac,bd)=f(a,b)f(c,d)。
给你一个二维积性函数 f,满足 f(x,y)=f(y,x)。
q 次询问,每次给定 n,m,求 ∑i=1n∑j=1mf(i,j)。答案对 109+7 取模。
输入格式
记 π(n) 为 1∼n 的质数个数,pi 为第 i 个质数。
第一行两个整数 N,q。
之后 π(N) 行,对于第 i 行,记 l=⌊logpiN⌋+1,一行读入 l2−1 个整数,第 j 个整数为 f(pi⌊lj⌋,pijmodl)。保证 f(x,y)=f(y,x)。
接下来 q 行,每行两个整数 n,m。
输出格式
q 行,每行一个整数表示答案对 109+7 取模后的结果。
6 6
2 3 2 4 5 3 5 6
7 7 8
9 9 10
1 1
2 2
3 3
4 4
5 5
6 6
1
9
59
123
367
837
提示
样例解释
| f(x,y) |
y=1 |
y=2 |
y=3 |
y=4 |
y=5 |
y=6 |
| x=1 |
1 |
2 |
7 |
3 |
9 |
14 |
| x=2 |
2 |
4 |
14 |
5 |
18 |
28 |
| x=3 |
7 |
14 |
8 |
21 |
63 |
16 |
| x=4 |
3 |
5 |
21 |
6 |
27 |
35 |
| x=5 |
9 |
18 |
63 |
27 |
10 |
126 |
| x=6 |
14 |
28 |
16 |
35 |
126 |
32 |
数据范围
1≤N,q≤1.5×105,1≤n,m≤N,1≤f(pia,pib)≤109。
| 子任务编号 |
N= |
q= |
分值 |
| 1 |
5000 |
10 |
| 2 |
30000 |
20 |
| 3 |
60000 |
| 4 |
100000 |
25 |
| 5 |
150000 |