33OJ
登录 注册

#P17819. 二维积性函数求和(many queries)

二维积性函数求和(many queries)

背景

板子。

题目描述

定义二维数论函数 f(x,y)f(x,y) 是积性函数,当且仅当对于所有 gcd⁡(ab,cd)=1\gcd(ab,cd)=1,都有 f(ac,bd)=f(a,b)f(c,d)f(ac,bd)=f(a,b)f(c,d)。

给你一个二维积性函数 ff,满足 f(x,y)=f(y,x)f(x,y)=f(y,x)。

qq 次询问,每次给定 n,mn,m,求 ∑i=1n∑j=1mf(i,j)\sum_{i=1}^n\sum_{j=1}^mf(i,j)。答案对 109+710^9+7 取模。

输入格式

记 π(n)\pi(n) 为 1∼n1\sim n 的质数个数,pip_i 为第 ii 个质数。

第一行两个整数 N,qN,q。

之后 π(N)\pi(N) 行,对于第 ii 行,记 l=⌊log⁡piN⌋+1l=\lfloor\log_{p_i}N\rfloor+1,一行读入 l2−1l^2-1 个整数,第 jj 个整数为 f(pi⌊jl⌋,pij mod l)f(p_i^{\lfloor\frac{j}{l}\rfloor},p_i^{j\bmod l})。保证 f(x,y)=f(y,x)f(x,y)=f(y,x)。

接下来 qq 行,每行两个整数 n,mn,m。

输出格式

qq 行,每行一个整数表示答案对 109+710^9+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)f(x,y) y=1y=1 y=2y=2 y=3y=3 y=4y=4 y=5y=5 y=6y=6
x=1x=1 11 22 77 33 99 1414
x=2x=2 22 44 1414 55 1818 2828
x=3x=3 77 1414 88 2121 6363 1616
x=4x=4 33 55 2121 66 2727 3535
x=5x=5 99 1818 6363 2727 1010 126126
x=6x=6 1414 2828 1616 3535 126126 3232

数据范围

1≤N,q≤1.5×1051\le N,q\le 1.5\times10^5,1≤n,m≤N1\le n,m\le N,1≤f(pia,pib)≤1091\le f(p_i^a,p_i^b)\le 10^9。

子任务编号 N=N= q=q= 分值
11 50005000 1010
22 3000030000 2020
33 6000060000
44 100000100000 2525
55 150000150000