P3700 [CQOI2017] table of small Q

Description

• There is a table with infinite rows and columns. The rows and columns start with \ (1 \), and the \ (a \) row \ (B \) column has an integer \ (f(a, b) \);
• \(f(a, b) \) shall meet:
  • \(\forall a, b \in \mathbb{N}^*, f(a, b) = f(b, a)\)；
  • \(\forall a, b\in \mathbb{N}^*, b\cdot f(a, a + b) = (a + b) \cdot f(a, b)\).
• Initially, \ (\ forall a, b\in \mathbb{N}^*, f(a, b) = ab \) (obviously this meets the requirements);
• \(m \) operations, giving \ (4 \) integers \ (a, b, x, k \) each time, indicating that \ (f(a, b) \gets x \), and then modifying all the lattices it can affect to ensure that the numbers of all lattices after modification are still integers. After modification, calculate the sum of all numbers in the \ (k \) column before the \ (k \) line \ (\ bmod (10^9 + 7) \);
• \(1 \le m \le 10^4, 1 \le a, b, k \le n \le 4 \times 10^6, 0 \le x < 10^{18}\).

Solution

For the nature \ (2 \), there will be no ideas directly.

We try to shift the term of the formula:

According to the nature \ (1 \), that is, when \ (a > b \), there are

Recall the formula of rolling Division:

It looks like it.

Let's transform this formula:

The last step in the rolling division method is

Here \ (a, b > 0 \) is required, i.e

Embodied in the original formula is

Namely

For query operations:

according to

It is found that \ (j \) may be greater than \ (i \), which can be multiplied by \ (2 \) according to symmetry.

However, all cases of \ (i = j \) are repeated \ (2 \) times; However, in the case of \ (i = j > 1 \), \ (\ gcd(i, j) \ne 1 \) will not contribute by itself; Only the case of \ (i = j = 1 \) is repeated.

In fact, the contribution of \ (i = j = 1 \) is \ (1\times 1\times 1 = 1 \), while \ (\ dfrac{1\times \varphi(1) + \varepsilon(1)}{2} \times 2 = 2 \), the solution is to throw away \ (\ varepsilon \) directly, so that \ (\ dfrac{1\times\varphi(1)}{2} \times 2 = 1 \) has no effect on the case of \ (I > 1 \).

To sum up,

Set it to \ (g(n) \) and find that \ (g \) can be answered by \ (\ Omicron(n) \) preprocessing \ (\ Omicron(1) \).

Substitutional formula

Divide the blocks happily.

If the prefix and sum of \ (f(n, n) \) are used in dividing blocks, the modification can be directly modified by a single point of the tree array, and the query is an interval query.

The query is \ (\ Omicron(m\sqrt{n} \log n) \), while the modification is \ (\ Omicron(m \log n) \). Although it can pass, it is very poor.

Consider what data structure can achieve \ (\ Omicron(1) \) query: Block - but only single point query.

It's not difficult to change the maintained things into prefix and. The query is \ (\ Omicron(1) \), and the modification is \ (\ gcd(a,b) \sim n \), which is \ (\ Omicron(\sqrt{n}) \).

Specifically, the title should be \ (f(a, b) \gets x \), which is based on the above formula

In this way, the balance is achieved - the modified queries are \ (\ Omicron(m\sqrt{n}) \), which is many times faster than the tree array.

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;
}