#3172. 日记和欧拉函数

日记和欧拉函数

题目限制

1000 ms 1024 M

题目描述

题目背景

数论中,有一个很重要的函数:φ\varphi。其定义为:φ(x)=i=1x[gcd(i,x)=1]\varphi(x) = \sum\limits_{i = 1}^{x} [\gcd (i, x) = 1],也就是 x\leq x 的正整数当中与 x 互质的数的个数。显然,除 11 以外,每个正整数 xx 都满足φ(x)<x \varphi(x) < x。 数论中,又有一种迭代函数:我们称 f(k)(x)=f(f(x))f^{(k)} (x) = f(\dots f(x)),恰好有 kkff。特别地,k0k\leq 0 时,定义 f(k)(x)=xf^{(k)} (x) = x。 日记想要把它们结合起来。

题目描述

日记认为,φ\varphi 函数不够美观。因此,日记定义了 f(x)=φ(m(x)B)(x)f(x) = \varphi^{(m(x)-B)} (x),其中 BB 为一个常数,m(x)=maxi=1mφ(i)m(x)=\max_{i=1}^{m}\varphi(i)

日记知道,有一种科技可以快速求出 φ\varphi 函数的区间和(即,i=LRφ(i)\sum\limits_{i=L}^{R} \varphi(i))。所以,她认定,也有一种科技可以快速求出 ff 函数的区间和(即,i=LRf(i)\sum\limits_{i=L}^{R} f(i))。但她太菜了,并不会这种科技。所以,她想请你帮个忙。

简要题意:先给定常数 B,TB, T,并给定 TTL,RL, R,求 i=LRφ(maxj=1iφ(j)B)(i)\sum\limits_{i=L}^{R} \varphi^{(\max_{j=1}^{i}\varphi(j)-B)} (i)

日记不会这种科技,数据怎么造的?

日记:暴力啊,但是你的程序只有 1s 的时间喵 /mgx

输入格式

11 行,22 个非负整数 T,BT, B,代表数据组数和常数。

接下来 TT 行,每行 22 个正整数 L,RL, R,代表你要求出 i=LRf(i)\sum\limits_{i=L}^{R} f(i) 的值。

输出格式

TT 行,每行 11 个正整数,代表答案。请注意,你可能需要 C++ 内置整型以外的类型来存储答案。

数据范围

本题设置 25 个测试点,每个测试点 4 分。同时,每个测试点满足一些限制,见下:

测试点编号 T=T= $ R \leq $ BB
11 33 1010
22 2020
33 100100
44 2020
55 10510^5
66 33 10310^3
77 2020
88 10510^5
99 33 3×1043\times 10^4
1010 2020
1111 10510^5 3×1043\times 10^4$
1212 3×1043\times 10^4
1313
1414 33 10610^6
1515 2020
1616 10510^5
1717
1818
1919 33 10910^9
2020
2121 10510^5 =0=0
2222 =109=10^9
2323
2424
2525

对全部数据,保证 1T1051 \leq T \leq 10^51LR1091 \leq L \leq R \leq 10^90B1090 \leq B \leq 10^9

输入样例 1

5 4
1 3
2 4
3 5
4 6
5 7

输出样例 1

6
9
12
15
13