|
P3700 [CQOI2017]小Q的表格
Description
- 有一个无穷多行，无穷多列的表格，行列从
1
1
1 开始标号，第
a
a
a 行
b
b
b 列有一个整数
f
(
a
,
b
)
f(a, b)
f(a,b)；
-
f
(
a
,
b
)
f(a, b)
f(a,b) 应满足：
-
?
a
,
b
∈
N
?
,
f
(
a
,
b
)
=
f
(
b
,
a
)
\forall a, b \in \mathbb{N}^*, f(a, b) = f(b, a)
?a,b∈N?,f(a,b)=f(b,a)；
-
?
a
,
b
∈
N
?
,
b
?
f
(
a
,
a
+
b
)
=
(
a
+
b
)
?
f
(
a
,
b
)
\forall a, b\in \mathbb{N}^*, b\cdot f(a, a + b) = (a + b) \cdot f(a, b)
?a,b∈N?,b?f(a,a+b)=(a+b)?f(a,b)。
- 初始时，
?
a
,
b
∈
N
?
,
f
(
a
,
b
)
=
a
b
\forall a, b\in \mathbb{N}^*, f(a, b) = ab
?a,b∈N?,f(a,b)=ab（显然这满足要求）；
-
m
m
m 次操作，每次给出
4
4
4 个整数
a
,
b
,
x
,
k
a, b, x, k
a,b,x,k，表示令
f
(
a
,
b
)
←
x
f(a, b) \gets x
f(a,b)←x，然后把它能够波及到的所有格子全部修改，保证修改之后所有格子的数仍然都是整数，修改完成后计算前
k
k
k 行前
k
k
k 列里所有数的和
?
m
o
d
?
(
1
0
9
+
7
)
\bmod (10^9 + 7)
mod(109+7)；
-
1
≤
m
≤
1
0
4
,
1
≤
a
,
b
,
k
≤
n
≤
4
×
1
0
6
,
0
≤
x
<
1
0
18
1 \le m \le 10^4, 1 \le a, b, k \le n \le 4 \times 10^6, 0 \le x < 10^{18}
1≤m≤104,1≤a,b,k≤n≤4×106,0≤x<1018。
Solution
对于性质
2
2
2，直接看是不会有任何思路的。
我们尝试对式子进行移项：
b
?
f
(
a
,
a
+
b
)
=
(
a
+
b
)
?
f
(
a
,
b
)
f
(
a
,
a
+
b
)
a
+
b
=
f
(
a
,
b
)
b
b\cdot f(a, a + b) = (a + b) \cdot f(a, b) \\ \dfrac{f(a, a + b)}{a + b} = \dfrac{f(a, b)}{b}
b?f(a,a+b)=(a+b)?f(a,b)a+bf(a,a+b)?=bf(a,b)?
根据性质
1
1
1，也就是说，当
a
>
b
a > b
a>b 时，有
f
(
a
,
b
)
a
=
f
(
b
,
a
?
m
o
d
?
b
)
a
?
m
o
d
?
b
\dfrac{f(a, b)}{a} = \dfrac{f(b, a \bmod b)}{a \bmod b}
af(a,b)?=amodbf(b,amodb)?
回忆辗转相除法的公式：
gcd
?
(
a
,
b
)
=
gcd
?
(
b
,
a
?
m
o
d
?
b
)
\gcd(a, b) = \gcd(b, a \bmod b)
gcd(a,b)=gcd(b,amodb)
发现和上面长的很像。
我们再把这个式子改造一下：
f
(
a
,
b
)
a
?
b
=
f
(
b
,
a
?
m
o
d
?
b
)
b
?
(
a
?
m
o
d
?
b
)
\dfrac{f(a, b)}{a \cdot b} = \dfrac{f(b, a\bmod b)}{b\cdot (a\bmod b)}
a?bf(a,b)?=b?(amodb)f(b,amodb)?
辗转相除法的最后一步是
gcd
?
(
a
,
b
)
=
gcd
?
(
gcd
?
(
a
,
b
)
,
0
)
\gcd(a, b) = \gcd(\gcd(a, b), 0)
gcd(a,b)=gcd(gcd(a,b),0)
而这里要求
a
,
b
>
0
a, b > 0
a,b>0，即
gcd
?
(
a
,
b
)
=
gcd
?
(
gcd
?
(
a
,
b
)
,
gcd
?
(
a
,
b
)
)
\gcd(a, b) = \gcd(\gcd(a, b), \gcd(a, b))
gcd(a,b)=gcd(gcd(a,b),gcd(a,b))
体现在原式中就是
f
(
a
,
b
)
a
?
b
=
f
(
gcd
?
(
a
,
b
)
,
gcd
?
(
a
,
b
)
)
gcd
?
(
a
,
b
)
2
\dfrac{f(a, b)}{a\cdot b} = \dfrac{f(\gcd(a, b), \gcd(a, b))}{\gcd(a, b)^2}
a?bf(a,b)?=gcd(a,b)2f(gcd(a,b),gcd(a,b))?
即
f
(
a
,
b
)
=
a
b
?
f
(
gcd
?
(
a
,
b
)
,
gcd
?
(
a
,
b
)
)
gcd
?
(
a
,
b
)
2
f(a, b) = \dfrac{ab\cdot f(\gcd(a, b), \gcd(a, b))}{\gcd(a, b)^2}
f(a,b)=gcd(a,b)2ab?f(gcd(a,b),gcd(a,b))?
对于查询操作：
a
n
s
=
∑
d
=
1
k
∑
i
=
1
k
∑
j
=
1
k
i
j
?
f
(
d
,
d
)
d
2
[
gcd
?
(
i
,
j
)
=
d
]
=
∑
d
=
1
k
f
(
d
,
d
)
∑
i
=
1
?
k
d
?
i
∑
j
=
1
?
k
d
?
j
[
gcd
?
(
i
,
j
)
=
1
]
\begin{aligned} ans & = \sum_{d = 1}^k \sum_{i = 1}^k \sum_{j = 1}^k \dfrac{ij\cdot f(d, d)}{d^2} [\gcd(i, j) = d] \\ & = \sum_{d = 1}^k f(d, d) \sum_{i = 1}^{\left\lfloor\frac{k}{d}\right\rfloor} i \sum_{j = 1}^{\left\lfloor\frac{k}{d}\right\rfloor} j [\gcd(i, j) = 1] \end{aligned}
ans?=d=1∑k?i=1∑k?j=1∑k?d2ij?f(d,d)?[gcd(i,j)=d]=d=1∑k?f(d,d)i=1∑?dk???ij=1∑?dk???j[gcd(i,j)=1]?
根据
n
∑
i
=
1
n
i
[
gcd
?
(
i
,
n
)
=
1
]
=
n
?
n
φ
(
n
)
+
ε
(
n
)
2
n \sum_{i = 1}^n i [\gcd(i, n) = 1] = n \cdot \dfrac{n \varphi(n) + \varepsilon(n)}{2}
ni=1∑n?i[gcd(i,n)=1]=n?2nφ(n)+ε(n)?
发现这里
j
j
j 可能大于
i
i
i，根据对称性乘
2
2
2 即可。
但所有
i
=
j
i = j
i=j 的情况都被重复算了
2
2
2 次；不过对于
i
=
j
>
1
i = j > 1
i=j>1 的情况，
gcd
?
(
i
,
j
)
≠
1
\gcd(i, j) \ne 1
gcd(i,j)?=1，本身不会产生贡献；只有
i
=
j
=
1
i = j = 1
i=j=1 的情况被重复算了。
实际上
i
=
j
=
1
i = j = 1
i=j=1 的贡献是
1
×
1
×
1
=
1
1\times 1\times 1 = 1
1×1×1=1，而
1
×
φ
(
1
)
+
ε
(
1
)
2
×
2
=
2
\dfrac{1\times \varphi(1) + \varepsilon(1)}{2} \times 2 = 2
21×φ(1)+ε(1)?×2=2，解决方案是直接把
ε
\varepsilon
ε 给扔掉，这样
1
×
φ
(
1
)
2
×
2
=
1
\dfrac{1\times\varphi(1)}{2} \times 2 = 1
21×φ(1)?×2=1 而且对于
i
>
1
i > 1
i>1 的情况去掉
ε
\varepsilon
ε 没有影响。
综上，
∑
i
=
1
n
i
∑
j
=
1
n
j
[
gcd
?
(
i
,
j
)
]
=
∑
i
=
1
n
i
?
i
φ
(
i
)
2
?
2
=
∑
i
=
1
n
i
2
φ
(
i
)
\begin{aligned} \sum_{i = 1}^n i \sum_{j = 1}^n j [\gcd(i, j)] & = \sum_{i = 1}^n i\cdot \dfrac{i \varphi(i)}{2} \cdot 2 \\ & = \sum_{i = 1}^n i^2 \varphi(i) \end{aligned}
i=1∑n?ij=1∑n?j[gcd(i,j)]?=i=1∑n?i?2iφ(i)??2=i=1∑n?i2φ(i)?
设其为
g
(
n
)
g(n)
g(n)，发现
g
g
g 可以
O
(
n
)
\Omicron(n)
O(n) 预处理
O
(
1
)
\Omicron(1)
O(1) 回答。
代回原式
a
n
s
=
∑
d
=
1
k
f
(
d
,
d
)
g
(
?
k
d
?
)
ans = \sum_{d = 1}^k f(d, d) g\left(\left\lfloor\dfrac{k}{d}\right\rfloor \right)
ans=d=1∑k?f(d,d)g(?dk??)
愉快地整除分块。
整除分块中要用到
f
(
n
,
n
)
f(n, n)
f(n,n) 的前缀和，那么修改直接用树状数组单点修改即可，查询就是区间查询。
查询是
O
(
m
n
log
?
n
)
\Omicron(m\sqrt{n} \log n)
O(mn
?logn) 的，而修改才
O
(
m
log
?
n
)
\Omicron(m \log n)
O(mlogn)，虽然能过但很不优。
考虑有什么数据结构能做到
O
(
1
)
\Omicron(1)
O(1) 查询：分块——但只能单点查询。
这也不难，把维护的东西改为前缀和，查询就是
O
(
1
)
\Omicron(1)
O(1)，修改就修改
gcd
?
(
a
,
b
)
～
n
\gcd(a,b) \sim n
gcd(a,b)～n，是
O
(
n
)
\Omicron(\sqrt{n})
O(n
?) 的。
具体地，题目中要
f
(
a
,
b
)
←
x
f(a, b) \gets x
f(a,b)←x，根据上面的公式就是
f
(
gcd
?
(
a
,
b
)
,
gcd
?
(
a
,
b
)
)
←
x
?
gcd
?
(
a
,
b
)
2
a
b
f(\gcd(a, b), \gcd(a, b)) \gets \dfrac{x \cdot \gcd(a, b)^2}{ab}
f(gcd(a,b),gcd(a,b))←abx?gcd(a,b)2?
这样就做到了平衡——修改查询均为
O
(
m
n
)
\Omicron(m\sqrt{n})
O(mn
?)，比树状数组不知道快了多少倍。
Code
#include <iostream>
#include <cstdio>
#include <cmath>
#define Debug(x) cout << #x << "=" << x << endl
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b) {return (a + b) % MOD;}
int sub(int a, int b) {return (a - b + MOD) % MOD;}
int mul(int a, int b) {return (ll)a * b % MOD;}
const int MAXN = 4e6 + 5;
typedef int arr[MAXN];
struct DS
{
arr L, R, belong, val, tag, a;
void build(int n)
{
int t = sqrt(n);
for (int i = 1; i <= t; i++)
{
L[i] = R[i - 1] + 1, R[i] = i * t;
}
if (R[t] < n)
{
t++;
L[t] = R[t - 1] + 1, R[t] = n;
}
for (int i = 1; i <= t; i++)
{
for (int j = L[i]; j <= R[i]; j++)
{
belong[j] = i;
a[j] = mul(j, j);
val[j] = add(val[j - 1], a[j]);
}
}
}
void update(int l, int r, int x)
{
int k = sub(x, a[l]);
a[l] = x;
int p = belong[l], q = belong[r];
if (p == q)
{
for (int i = l; i <= r; i++)
{
val[i] = add(val[i], k);
}
}
else
{
for (int i = l; i <= R[p]; i++)
{
val[i] = add(val[i], k);
}
for (int i = L[q]; i <= r; i++)
{
val[i] = add(val[i], k);
}
for (int i = p + 1; i < q; i++)
{
tag[i] = add(tag[i], k);
}
}
}
int query(int x)
{
return add(val[x], tag[belong[x]]);
}
int GetSum(int l, int r)
{
return sub(query(r), query(l - 1));
}
}D;
struct Math
{
arr p, phi, g;
bool vis[MAXN];
void pre(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= p[0] && i * p[j] <= n; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
for (int i = 1; i <= n; i++)
{
g[i] = add(g[i - 1], mul(mul(i, i), phi[i]));
}
}
int gcd(int a, int b)
{
if (!b)
{
return a;
}
return gcd(b, a % b);
}
int block(int n)
{
int res = 0;
for (int l = 1, r; l <= n; l = r + 1)
{
int k = n / l;
r = n / k;
res = add(res, mul(D.GetSum(l, r), g[k]));
}
return res;
}
}M;
int main()
{
int m, n;
scanf("%d%d", &m, &n);
D.build(n), M.pre(n);
while (m--)
{
int a, b, k; ll xx;
scanf("%d%d%lld%d", &a, &b, &xx, &k);
int d = M.gcd(a, b);
xx = xx / (a / d) / (b / d);
int x = xx % MOD;
D.update(d, n, x);
printf("%d\n", M.block(k));
}
return 0;
}
|