BZOJ 4815 - [Cqoi2017]小Q的表格

#数学 #数论 #分块 #数据结构

Published on 2017-05-03

题目描述

描述

小Q是个程序员。

作为一个年轻的程序员，小Q总是被老C欺负，老C经常把一些麻烦的任务交给小Q来处理。每当小Q不知道如何解决

时，就只好向你求助。为了完成任务，小Q需要列一个表格，表格有无穷多行，无穷多列，行和列都从 $1$ 开始标号。

为了完成任务，表格里面每个格子都填了一个整数，为了方便描述，小Q把第 $a$ 行第 $b$ 列的整数记为 $f(a,b)$ ，为了完成任务，这个表格要满足一些条件：

对任意的正整数 $a,b$ ，都要满足 $f(a,b)=f(b,a)$ ；
对任意的正整数 $a,b$ ，都要满足 $b\times f(a,a+b)=(a+b)\times f(a,b)$ 。

为了完成任务，一开始表格里面的数很有规律，第 $a$ 行第 $b$ 列的数恰好等于 $ab$ 。显然一开始是满足上述两个条件的。为了完成任务，小Q需要不断的修改表格里面的数，每当修改了一个格子的数之后，为了让表格继续满足上述两个条件，小Q还需要把这次修改能够波及到的全部格子里都改为恰当的数。由于某种神奇的力量驱使，已经确保了每一轮修改之后所有格子里的数仍然都是整数。为了完成任务，小Q还需要随时获取前 $k(k\le 4\times{10}^6)$ 行前 $k$ 列这个有限区域内所有数的和是多少，答案可能比较大，只需要算出答案 $\bmod {10}^9 + 7$ 之后的结果。

分析

这个题看上去十分的棘手，因为每次修改，可能会影响很多的位置，如果不能发现一个简洁的规律，无从下手的。

我们观察哪些位置同属于一个类，同一类中的任意一个位置的值改变，同类中其他的位置的值都改变。首先根据条件一， $(a, b)$ 和 $(b, a)$ 属于同一类。再根据条件二，可以得到 $(a, a + b)$ 和 $(a, b)$ 属于同一类，这可以改写为 $(a, c)(c > a)$ 和 $(a, c - a)$ 属于同一类。

由此可以看出辗转相减法的影子，不难得到，所有 $\gcd(a, b) = g$ 的 $(a,b)$ 同属于一类。也就是说，改变了 $(a, b)$ 位置的值，那么 $\gcd(a, b)$ 这整个类的所有位置的值都会改变。

进一步找规律，我们发现所有 $\gcd(a, b) = g$ 的 $f(a, b)$ 都可以写成 $f(g, g)$ 的倍数，更具体的，有

f(a\cdot g, b\cdot g) = a\cdot b\cdot f(g, g), \quad\gcd(a, b) = 1

可以用归纳法证明这一结论。由此，我们每次询问的答案就可以转化为下面和式的值

\sum_{d = 1}^kf(d, d)\sum_{i = 1}^{\lfloor\frac k d\rfloor}\sum_{j = 1}^{\lfloor\frac k d\rfloor}i\cdot j[\gcd(i, j) = 1]

由于 $\lfloor\frac k d\rfloor$ 的存在，这个式子可以被分为 $O(\sqrt n)$ 段，每一段中 $\lfloor\frac k d\rfloor$ 的值相同，我们需要快速求 $f(d, d)$ 的一段区间和，并且支持单点修改。注意到有 $O(m\sqrt n)$ 次询问，却只有 $O(m)$ 次修改，我们设计一个 $O(\sqrt n)$ 修改 $O(1)$ 查询的分块结构即可做到总时间复杂度 $O(m\sqrt n)$ 。

现在唯一的问题是求后面的一个和式，由于两个上指标相同，所以这个和式应该是十分容易求出的

\begin{aligned} &\sum_{i = 1}^n\sum_{j = 1}^ni\cdot j[\gcd(i, j) = 1]\\ =&2(\sum_{i = 1}^n\sum_{j = 1}^ii\cdot j[\gcd(i, j) = 1]) - \sum_{1\le i = j\le n}^ni \cdot j[\gcd(i, j) = 1]\\ =&2(\sum_{i = 1}^ni\sum_{j = 1}^ij[\gcd(i, j) = 1]) - 1\\ =&2(\sum_{i = 1}^ni\cdot\frac {i\cdot\varphi(i) + [i = 1]}2) - 1\\ =&\sum_{i = 1}^ni^2\cdot\varphi(i) \end{aligned}

其中第三个等号运用了 BZOJ 2226 中的技巧。线筛出 $\varphi(n)$ 后，即可 $O(n)$ 预处理出这个和式在 $1\sim n$ 处的值。在询问的过程中，还需要用到 $1\sim n$ 的逆元来得到 $f(g, g)$ 的值， $O(n)$ 递推预处理即可。

总复杂度 $O(n + m\sqrt n)$ 。

代码

//  Created by Sengxian on 2017/05/03.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 4815 数论
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline ll readLL() {
    ll n = 0;
    int ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 4000000 + 3, MOD = 1000000007;
int primes[MAX_N], cnt = 0;
bool isNotPrime[MAX_N];
int phi[MAX_N], f[MAX_N], inv[MAX_N];

void sieve(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) primes[cnt++] = i, phi[i] = i - 1;
        for (int j = 0; j < cnt && i * primes[j] <= n; ++j) {
            int t = i * primes[j];
            isNotPrime[t] = true;
            if (i % primes[j] == 0) {
                phi[t] = phi[i] * primes[j];
                break;
            } else phi[t] = phi[i] * (primes[j] - 1);
        }
    }

    inv[1] = 1;
    for (int i = 2; i <= n; ++i) inv[i] = ((-(ll)(MOD / i) * inv[MOD % i] % MOD) + MOD) % MOD;
}

int force(int n) {
    int res = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            res += i * j * (__gcd(i, j) == 1);
    return res;
}

void prepare(int n) {
    sieve(n);
    f[1] = 1;
    for (int i = 2; i <= n; ++i) f[i] = (f[i - 1] + (ll)i * i % MOD * phi[i]) % MOD;
}

struct Block {
    static const int BLOCK_CNT = 2000 + 3;
    int n, bel[MAX_N], blockSize;
    ll s[MAX_N], tag[BLOCK_CNT];

    void init(int _n, int *a) {
        n = _n + 1;
        for (int i = 1; i < n; ++i) s[i] = (s[i - 1] + a[i]) % MOD;
        memset(tag, 0, sizeof tag);
        blockSize = ceil(sqrt(n));
        for (int i = 0; i < n; ++i) bel[i] = i / blockSize;
    }

    inline void add(int pos, int x) {
        int blockID = bel[pos], right = min((blockID + 1) * blockSize, n);
        for (int i = pos; i < right; ++i) s[i] += x;
        for (int i = blockID + 1; i <= bel[n - 1]; ++i) tag[i] += x;
    }

    inline int sum(int pos) {
        return (s[pos] + tag[bel[pos]]) % MOD;
    }
} block;

int v[MAX_N];

int calc(int n) {
    int ans = 0;
    for (int i = 1, j = 0; i <= n; i = j + 1) {
        j = n / (n / i);
        (ans += (ll)(block.sum(j) - block.sum(i - 1)) * f[n / i] % MOD) %= MOD;
    }
    return (ans + MOD) % MOD;
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    int m = readLL(), n = readLL();

    prepare(n);
    for (int i = 1; i <= n; ++i) v[i] = (ll)i * i % MOD;
    block.init(n, v);

    for (int i = 0; i < m; ++i) {
        int a = readLL(), b = readLL(), g = __gcd(a, b);
        int res = readLL() % MOD * inv[a / g] % MOD * inv[b / g] % MOD;
        block.add(g, res - v[g]), v[g] = res;
        printf("%d\n", calc(readLL()));
    }

    return 0;
}

BZOJ 4820 - [Sdoi2017]硬币游戏 BZOJ 4871 - [Shoi2017]摧毁“树状图”

Sengxian's Blog

BZOJ 4815 - [Cqoi2017]小Q的表格

描述

分析

代码