8.26 T2 日记和欧拉函数（欧拉函数）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141575260

http://cplusoj.com/d/senior/p/NOD2301B

发现 x≤Bx\le B 时答案是 xx

x>B+500x>B+500 左右答案是1

我们预处理中间的就行

预处理直接暴力做，求 max⁡ϕ\max \phi 的话相当于求小于它的质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 510
int n, m, i, j, k, T, B;
int mx, phi[N], f[N], sm[N], l, r;
int ans;  
map<int, int>mp; 

int qry(int x) {
	if(mp[x]) return mp[x]; 
	int ans = 1, i, j; 
//	debug("phi[%lld] = ", x); 
	for(i = 2; i * i <= x; ++i) 
		if(x % i == 0) {
			j = 1; 
			while(x % i == 0) 
				x /= i, j *= i; 
			j /= i; j *= (i - 1); 
			ans *= j; 
		}
	if(x > 1) ans *= (x - 1); 
//	debug("%lld\n", ans); 
	return mp[x] = ans; 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	T = read(); B = read(); 
	for(j = 1 + B; ; --j) if(j == 1 || qry(j) == j - 1) break; 
//	debug("Out\n"); 
	for(i = 1; i <= 400; ++i) {
		k = i + B; phi[i] = qry(k); 
		if(phi[i] == k - 1) j = k; 
		mx = j - 1 - B; f[i] = k; 
		if(i <= 6) debug("[%lld]%lld %lld | %lld\n", k, mx, phi[i], j); 
		if(mx <= 0) continue; 
		while(mx-- && f[i] != 1) f[i] = qry(f[i]); 
		if(i <= 6) debug("[%lld] %lld\n", k, f[i]); 
	}
	for(i = 1; i <= 400; ++i) sm[i] = sm[i - 1] + f[i]; 
	while(T--) {
		l = read(); r = read(); ans = 0; 
		if(r <= B) { printf("%lld\n", (l + r) * (r - l + 1) / 2); continue; }
		if(l <= B) ans += (l + B) * (B - l + 1) / 2, l = B + 1; 
		if(l >= B + 400) { printf("%lld\n", r - l + 1); continue; }
		if(r >= B + 400) ans += (r - (B + 400) + 1), r = B + 400 - 1; 
		debug("[%lld %lld] %lld\n", l, r, ans); 
		l -= B; r -= B; ans += sm[r] - sm[l - 1]; 
		debug("[%lld %lld]\n", l, r); 
		printf("%lld\n", ans); 
	}
	return 0;
}