题面：整数分块again
大秦 为你打开 题目传送门
备用题面
看不了题目的看下面喵！
给出 $N$ 并计算下面表达式的值：
答案对于 $M$ 取模。
思路
拿到题面，注意到整数分块的经典部分，不难写出如下代码：
1
2
3
4
5
6
7
8
9
| inline void Work() {
ll ans = 0;
for(ll l = 1, r = 1; r <= n; l = r + 1) {
r = n / (n / l);
(ans += ((f(r) - f(l - 1) + P) % P) * (n / l) % P) %= P;
if(r == n) break;
}
printf("%lld\n", ans);
}
|
那么这题主要的考点，其实就是计算一段区间内的四次方和。借助强大的搜索引擎我们可以轻松知道四次方和前缀和公式是：
当我看到这个式子的时候，想都没有想直接上逆元，因为众所周知取模除法可以表示为 $a\div b\equiv a\times b^{-1}\pmod P$ 其中根据费马小可以知道 $b^{-1}\equiv b^{P-2}$ 当然前提是 $P$ 是质数。不过非常遗憾，这道题关于模数并没有好的性质，比如说 $P$ 是质数啊，$30\perp P$ 啊之类的，他全都没有，所以说用逆元来计算这玩意也不太行。
事实上可以用 $30\times P$ 代替模数进行运算，接下来给出关于这个代替方式的证明以及一些要求。
首先抽象一下题目意思，目前要计算的问题是 $(a\div b)\bmod P$ 的结果。
第一步我们可以根据整数除法，将 $a$ 拆分为 $a=k\times (bP)+r\ (0\le r\lt bP)$ 。
然后我们分开计算 $(a\div b)\bmod P$ 和 $((a\bmod bP)\div b)\bmod P$。
最后相等了。但是有一个要注意的地方是，$b\mid r$ 也就是 $b$ 可以整除 $r$（不然的话分数不能直接参与模运算，你还是得算逆元……）
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
ll n, P;
inline void Input() {
read(n, P);
}
inline ll Pow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % P;
a = a * a % P;
b = b >> 1;
}
return ans;
}
ll P2, f1, f2, f3, f4;
inline ll f(ll n) {
P2 = 30 * P;
f1 = n % P2;
f2 = (n + 1) % P2;
f3 = (n * 2 + 1) % P2;
f4 = ((3 * n % P2 * n + 3 * n % P2) % P2 - 1 + P2) % P2;
return ((f1 * f2 % P2 * f3 % P2 * f4 % P2) / 30) % P;
}
inline void Work() {
ll ans = 0, lst = 0, now = 0;
for(ll l = 1, r = 1; r <= n; l = r + 1) {
r = n / (n / l); now = f(r);
(ans += ((now - lst + P) % P) * (n / l) % P) %= P;
lst = now;
if(r == n) break;
}
printf("%lld\n", ans);
}
int main() {
int T = read(), ca = 0;
while(T--) {
Input();
Work();
}
return 0;
}
|
