33OJ
登录 注册

#P17818. gcd sum?

gcd sum?

题目描述

qq 次询问,每次给定 l1,r1,l2,r2l_1,r_1,l_2,r_2,求 ∑i=l1r1∑j=l2r2gcd⁡(i,j)\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}\gcd(i,j),答案对 109+710^9+7 取模。

输入格式

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

接下来 qq 行,每行四个整数 l1,r1,l2,r2l_1,r_1,l_2,r_2。

输出格式

qq 行,每行一个整数表示答案对 109+710^9+7 取模后的结果。

3 2
1 2 1 2
2 3 1 2
5
5

提示

数据范围

1≤N,q≤3×1051\le N,q\le 3\times10^5,1≤l1≤r1≤N1\le l_1\le r_1\le N,1≤l2≤r2≤N1\le l_2\le r_2\le N。

子任务编号 N=N= q=q= 分值
11 5000050000 1010
22 150000150000 4040
33 300000300000 5050