『题解』Luogu-P3700 [CQOI2017]小Q的表格

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

//18 = 9 + 9 = 18.
#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;
}
上一篇:南阳理工oj88--汉诺塔(一)


下一篇:数论同余学习笔记 Part 2