#P17818. gcd sum?
gcd sum?
题目描述
次询问,每次给定 ,求 ,答案对 取模。
输入格式
第一行两个整数 。
接下来 行,每行四个整数 。
输出格式
行,每行一个整数表示答案对 取模后的结果。
3 2
1 2 1 2
2 3 1 2
5
5
提示
数据范围
,,。
| 子任务编号 | 分值 | ||
|---|---|---|---|
q 次询问,每次给定 l1,r1,l2,r2,求 ∑i=l1r1∑j=l2r2gcd(i,j),答案对 109+7 取模。
第一行两个整数 N,q。
接下来 q 行,每行四个整数 l1,r1,l2,r2。
q 行,每行一个整数表示答案对 109+7 取模后的结果。
3 2
1 2 1 2
2 3 1 2
5
5
1≤N,q≤3×105,1≤l1≤r1≤N,1≤l2≤r2≤N。
| 子任务编号 | N= | q= | 分值 |
|---|---|---|---|
| 1 | 50000 | 10 | |
| 2 | 150000 | 40 | |
| 3 | 300000 | 50 | |