该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目限制
1000 ms 1024 M
题目描述
题目背景
数论中,有一个很重要的函数:φ。其定义为:φ(x)=i=1∑x[gcd(i,x)=1],也就是 ≤x的正整数当中与 x 互质的数的个数。显然,除 1 以外,每个正整数 x 都满足φ(x)<x。
数论中,又有一种迭代函数:我们称 f(k)(x)=f(…f(x)),恰好有 k 个 f。特别地,k≤0 时,定义 f(k)(x)=x。
日记想要把它们结合起来。
题目描述
日记认为,φ 函数不够美观。因此,日记定义了 f(x)=φ(m(x)−B)(x),其中 B 为一个常数,m(x)=maxi=1mφ(i)。
日记知道,有一种科技可以快速求出 φ 函数的区间和(即,i=L∑Rφ(i))。所以,她认定,也有一种科技可以快速求出 f 函数的区间和(即,i=L∑Rf(i))。但她太菜了,并不会这种科技。所以,她想请你帮个忙。
简要题意:先给定常数 B,T,并给定 T 组 L,R,求 i=L∑Rφ(maxj=1iφ(j)−B)(i)。
日记不会这种科技,数据怎么造的?
日记:暴力啊,但是你的程序只有 1s 的时间喵 /mgx
输入格式
第 1 行,2 个非负整数 T,B,代表数据组数和常数。
接下来 T 行,每行 2 个正整数 L,R,代表你要求出 i=L∑Rf(i) 的值。
输出格式
T 行,每行 1 个正整数,代表答案。请注意,你可能需要 C++ 内置整型以外的类型来存储答案。
数据范围
本题设置 25 个测试点,每个测试点 4 分。同时,每个测试点满足一些限制,见下:
测试点编号 |
T= $ |
R \leq $ |
B |
1 |
3 |
10 |
|
2 |
20 |
3 |
100 |
4 |
20 |
5 |
105 |
6 |
3 |
103 |
7 |
20 |
8 |
105 |
9 |
3 |
3×104 |
10 |
20 |
11 |
105 |
3×104$ |
12 |
3×104 |
13 |
14 |
3 |
106 |
15 |
20 |
16 |
105 |
17 |
18 |
19 |
3 |
109 |
20 |
21 |
105 |
=0 |
22 |
=109 |
23 |
|
24 |
25 |
对全部数据,保证 1≤T≤105,1≤L≤R≤109,0≤B≤109。
输入样例 1
5 4
1 3
2 4
3 5
4 6
5 7
输出样例 1
6
9
12
15
13