[CQOI2017]小Q的表格

题目描述

给定一个表格，满足：

$\forall a,b\;f(a,b)=f(b,a)$
$\forall a,b\;b\cdot f(a,a+b)=(a+b)\cdot f(a,b)$

有 $m$ 次操作

每次操作修改 $f(a,b)$ 的值，为了使整个表满足条件，所以要修改的点还挺多的
然后让你输出 $k*k$ 的范围内的数的和

Solution

对于性质 $\forall a,b\;b\cdot f(a,a+b)=(a+b)\cdot f(a,b)$ ，观察发现它可以转化一下：

$\begin{align*} b\cdot f(a,a+b)&=(a+b)\cdot f(a,b)\\ \Leftrightarrow ab\cdot f(a,a+b)&=a(a+b)\cdot f(a,b)\\ \Leftrightarrow\quad\;\frac{f(a,a+b)}{a(a+b)}&=\frac{f(a,b)}{ab}\\ \Leftrightarrow\qquad\;\;\;\frac{f(a,b)}{a,b}&=\frac{f(\gcd(a,b), \gcd(a,b))}{\gcd^2(a,b)} \end{align*}$

对于转化到 $\gcd(a,b)$ 不太理解的同学，可以看看这个结论

这里就不细说了

所以可以得到一个结论：

$\begin{align*} f(a,b)&=f(gcd(a,b),gcd(a,b))\times\frac{ab}{\gcd^2(a,b)}\\ &=g(d)\times\frac{ab}{d^2} \end{align*}$

为了方便后文描述，这里就记 $g(d)=f(d,d)$

那么就得到了一个线性的表了

那么再回头看看题目要求的问题

$\begin{align*} ans&=\sum_{d=1}^ng(d)\sum_{i=1}^n\sum_{j=1}^n\frac{ij}{\gcd^2(i,j)}[\gcd(i,j)=d]\\ &=\sum_{d=1}^ng(d)\sum_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left\lfloor\frac md\right\rfloor}ij[\gcd(i,j)=1]\\ &=\sum_{d=1}^ng(d)\sum_{i=1}^{\left\lfloor\frac nd\right\rfloor}i\sum_{j=1}^{\left\lfloor\frac nd\right\rfloor}j[\gcd(i,j)=1]\\ \end{align*}$

考虑:

$\sum_{i=1}^ni[\gcd(i,n)=1]=\frac{n\times\varphi(n)}{2}$

所以原式可以化为:

$ans= \sum_{d=1}^ng(d)\sum_{i=1}^{\left\lfloor\frac nd\right\rfloor}i^2\varphi(i)$

那么这个时候我们发现，后面的 $\sum_{i=1}^\sqrt ni^2\varphi(i)$ 是可以直接 $O(1)$ 求解的（先预处理，就可以直接查询）

然而前面那个 $g(d)$ 是会发生改变的

这个可以用树状数组或者是分块来维护

这两个理论上是可以过的，实测再loj是可以过的

某些 $oj$ 上确实过不了的

时间复杂度理论上可以接受，具体能否跑过就靠评测姬了啊

Code(树状数组)

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)

using namespace std;

typedef long long ll;
const ll maxn = 4e6 + 10;
const ll mod = 1e9 + 7;

inline ll __read() {
    ll x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = ((x << 1) + (x << 3) + (o ^ 48)) % mod;
    return x % mod;
}

ll size, n, q, len;
ll pr[maxn], phi[maxn], f[maxn], cnt;
ll id[maxn], st[maxn], ed[maxn];
ll val[maxn], sum[maxn], Sum[maxn];
bool vis[maxn];

inline void inc(ll &x, ll y) {
    x += y;
    if (x >= mod)
        x -= mod;
    else if (x < 0)
        x += mod;
}

inline ll add(ll x, ll y) {
    ll temp = x + y;
    if (temp >= mod)
        temp -= mod;
    else if (temp < 0)
        temp += mod;
    return temp;
}

inline ll Pow(ll x, ll y) {
    ll ans(1);
    while (y) {
        if (y & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans % mod;
}

ll Gcd(ll x, ll y) {
    if (!y)
        return x;
    return Gcd(y, x % y);
}

inline void Update(ll x, ll val) {
    while (x <= n) {
        inc(sum[x], val);
        x += lowbit(x);
    }
}

inline ll Query(ll x) {
    ll ans(0);
    while (x) {
        inc(ans, sum[x]);
        x -= lowbit(x);
    }
    return ans % mod;
}

inline ll Query(ll l, ll r) { return add(Query(r), -1ll * Query(l - 1)); }

inline void init() {
    phi[1] = 1;
    for (ll i = 2; i <= n; ++i) {
        if (!vis[i])
            pr[++cnt] = i, phi[i] = i - 1;
        for (ll j = 1; j <= cnt && i * pr[j] <= n; ++j) {
            vis[i * pr[j]] = 1;
            if (i % pr[j]) {
                phi[i * pr[j]] = phi[i] * phi[pr[j]];
            } else {
                phi[i * pr[j]] = phi[i] * pr[j];
                break;
            }
        }
    }

    for (ll i = 1; i <= n; ++i) f[i] = (f[i - 1] + i * i % mod * phi[i] % mod) % mod;
}

signed main() {
    q = __read(), n = __read();
    init();

    for (ll i = 1; i <= n; ++i) {
        val[i] = 1ll * i * i % mod;
        Update(i, val[i]);
    }

    while (q--) {
        ll a = __read(), b = __read(), x = __read(), k = __read(), d = Gcd(a, b);

        ll upt = x * d % mod * d % mod * Pow(1ll * a * b % mod, mod - 2) % mod;
        Update(d, add(upt, -val[d]));
        val[d] = upt;

        ll ans(0);
        for (ll l = 1, r; l <= k; l = r + 1) {
            r = k / (k / l);
            inc(ans, f[k / l] * Query(l, r) % mod);
        }

        printf("%lld\n", ans);
    }
}

Code(分块)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll maxn = 4e6 + 10;
const ll mod = 1e9 + 7;

inline ll __read() {
    ll x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = ((x << 1) + (x << 3) + (o ^ 48)) % mod;
    return x % mod;
}

ll size, n, q, len;
ll pr[maxn], phi[maxn], f[maxn], cnt;
ll id[maxn], st[maxn], ed[maxn];
ll val[maxn], sum[maxn], Sum[maxn];
bool vis[maxn];

inline void inc(ll &x, ll y) {
    x += y;
    if (x >= mod)
        x -= mod;
}

inline ll add(ll x, ll y) {
    ll temp = x + y;
    if (temp >= mod)
        temp -= mod;
    return temp;
}

inline ll Pow(ll x, ll y) {
    ll ans(1);
    while (y) {
        if (y & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans % mod;
}

ll Gcd(ll x, ll y) {
    if (!y)
        return x;
    return Gcd(y, x % y);
}

inline ll Get_sum(ll x) {
    if (!x)
        return 0;
    return add(Sum[id[x] - 1], sum[x]);
}

inline ll Get_sum(ll l, ll r) { return ((Get_sum(r) - Get_sum(l - 1)) % mod + mod) % mod; }

inline void init() {
    phi[1] = 1;
    for (ll i = 2; i <= n; ++i) {
        if (!vis[i])
            pr[++cnt] = i, phi[i] = i - 1;
        for (ll j = 1; j <= cnt && i * pr[j] <= n; ++j) {
            vis[i * pr[j]] = 1;
            if (i % pr[j]) {
                phi[i * pr[j]] = phi[i] * phi[pr[j]];
            } else {
                phi[i * pr[j]] = phi[i] * pr[j];
                break;
            }
        }
    }

    for (ll i = 1; i <= n; ++i) f[i] = (f[i - 1] + i * i % mod * phi[i] % mod) % mod;
}

inline void Update(ll x) {
    if (x == st[id[x]])
        sum[x] = val[x];
    else
        sum[x] = sum[x - 1] + val[x];
    for (ll i = x + 1; i <= ed[id[x]]; ++i) sum[i] = add(sum[i - 1], val[i]);
    for (ll i = id[x]; i <= len; ++i) Sum[i] = add(Sum[i - 1], sum[ed[i]]);
}

signed main() {
    q = __read(), n = __read();
    size = sqrt(n);
    init();

    for (ll i = 1; i <= n; ++i) {
        id[i] = i / size + 1;
        if (i % size)
            continue;
        st[id[i]] = i, ed[id[i] - 1] = i - 1;
    }
    len = id[n], ed[id[n]] = n;

    for (ll i = 1; i <= n; ++i) val[i] = 1ll * i * i % mod;

    for (ll i = 1; i <= len; ++i) {
        sum[st[i]] = val[st[i]];
        for (ll j = st[i] + 1; j <= ed[i]; ++j) sum[j] = add(sum[j - 1], val[j]);
        Sum[i] = add(Sum[i - 1], sum[ed[i]]);
    }

    while (q--) {
        ll a = __read(), b = __read(), x = __read(), k = __read(), d = Gcd(a, b);

        val[d] = x * d % mod * d % mod * Pow(1ll * a * b % mod, mod - 2) % mod;

        Update(d);

        ll ans(0);
        for (ll l = 1, r; l <= k; l = r + 1) {
            r = k / (k / l);
            inc(ans, f[k / l] * Get_sum(l, r) % mod);
        }

        printf("%lld\n", ans);
    }
}

进一步考虑

我们每次修改的值其实是 $f(\gcd(a,b))$ ，所以真时要改的值并不多

那么我们可以先求出原表中 $k*k$ 范围内的值
再求出修改的值对答案贡献相对原来的偏移量

$\Delta ans=\sum_{i=1}^{cnt}(改(i)-原^2(i))\sum_{j=1}^{\left\lfloor\frac ki\right\rfloor}j^2\varphi(j)$

所以这个就是 $O(cnt)$ 的复杂度

然后又是可以证明对于所有的 $\gcd(n,m)$ 的个数时处于 $\log n\sim\sqrt n$ 这个级别的

所以修改大概就是 $O(m\log n)\sim O(m\sqrt n)$

然而实际跑下来要比这快得多

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll maxn = 4e6 + 10;
const ll mod = 1e9 + 7;

inline ll __read() {
    ll x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

ll size, n, q, len;
ll pr[maxn], phi[maxn], f[maxn], cnt;
ll stk[maxn], upt[maxn], top;
bool vis[maxn], che[maxn];

inline void init() {
    phi[1] = 1;
    for (ll i = 2; i <= n; ++i) {
        if (!vis[i])
            pr[++cnt] = i, phi[i] = i - 1;
        for (ll j = 1; j <= cnt && i * pr[j] <= n; ++j) {
            vis[i * pr[j]] = 1;
            if (i % pr[j]) {
                phi[i * pr[j]] = phi[i] * phi[pr[j]];
            } else {
                phi[i * pr[j]] = phi[i] * pr[j];
                break;
            }
        }
    }
    for (ll i = 1; i <= n; ++i) f[i] = (f[i - 1] + i * i % mod * phi[i] % mod) % mod;
}

inline ll sum(ll x) { return x * (x + 1) / 2 % mod; }

ll gcd(ll x, ll y) {
    if (!y)
        return x;
    return gcd(y, x % y);
}

signed main() {
    q = __read(), n = __read();
    init();
    while (q--) {
        ll a = __read(), b = __read(), x = __read(), k = __read(), d = gcd(a, b);

        upt[d] = x / (a / d) / (b / d) % mod;
        if (!che[d]) {
            stk[++top] = d;
            che[d] = 1;
        }

        ll ans(sum(k));
        ans = ans * ans % mod;

        for (ll i = 1; i <= top; ++i) {
            d = stk[i];
            ans = (ans + ((upt[d] - d * d % mod) % mod + mod) % mod * f[k / d] % mod) % mod;
        }
        printf("%lld\n", ans);
    }
}