P3700 [CQOI2017]小Q的表格(反演、分块)

P3700 [CQOI2017]小Q的表格

给定一个大小为 n × n n \times n n×n的表格,初始时 i , j i, j i,j位置上填的是 f ( i , j ) = i × j f(i, j) = i \times j f(i,j)=i×j,有 m m m个操作,每次操作给定 a , b , x , k a, b, x, k a,b,x,k,把格子 a , b a, b a,b上的值改成 x x x,求 ∑ i = 1 k ∑ j = 1 k f ( i , j ) \sum\limits_{i = 1} ^{k} \sum\limits_{j = 1} ^{k} f(i, j) i=1∑k​j=1∑k​f(i,j)。

我们定义,在任何时刻,表格里的值都满足 f ( i , j ) = f ( j , i ) , j × f ( i , i + j ) = ( i + j ) × f ( i , j ) f(i, j) = f(j, i), j \times f(i, i + j) = (i + j) \times f(i, j) f(i,j)=f(j,i),j×f(i,i+j)=(i+j)×f(i,j)。
b × f ( a , a + b ) = ( a + b ) × f ( a , b ) f ( a , a + b ) a × ( a + b ) = f ( a , b ) a × b f ( a , b ) a × b = f ( b , a   %   b ) b × a   %   b f ( a , b ) a × b = f ( d , d ) d × d , d = gcd ⁡ ( a , b ) f ( a , b ) = a × b d × d f ( d , d ) b \times f(a, a + b) = (a + b) \times f(a, b)\\ \frac{f(a, a + b)}{a \times (a + b)} = \frac{f(a, b)}{a \times b}\\ \frac{f(a, b)}{a \times b} = \frac{f(b, a\ \%\ b)}{b \times a\ \%\ b}\\ \frac{f(a, b)}{a \times b} = \frac{f(d, d)}{d \times d}, d = \gcd(a, b)\\ f(a, b) = \frac{a \times b}{d \times d} f(d, d)\\ b×f(a,a+b)=(a+b)×f(a,b)a×(a+b)f(a,a+b)​=a×bf(a,b)​a×bf(a,b)​=b×a % bf(b,a % b)​a×bf(a,b)​=d×df(d,d)​,d=gcd(a,b)f(a,b)=d×da×b​f(d,d)

考虑统计答案:
∑ i = 1 n ∑ j = 1 n f ( i , j ) ∑ d = 1 n f ( d , d ) ∑ i = 1 n d ∑ j = 1 n d i j [ gcd ⁡ ( i , j ) = 1 ] ∑ d = 1 n f ( d , d ) ( ∑ i = 1 n d i ∑ j = 1 i j [ gcd ⁡ ( i , j ) − 1 ] − 1 ) ∑ d = 1 n f ( d , d ) ∑ i = 1 n d i 2 ϕ ( i ) g ( n ) = ∑ i = 1 n i 2 × ϕ ( i ) \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} f(i, j)\\ \sum_{d = 1} ^{n} f(d, d) \sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{\frac{n}{d}} ij[\gcd(i, j) = 1]\\ \sum_{d = 1} ^{n} f(d, d) \left(\sum_{i = 1} ^{\frac{n}{d}} i \sum_{j = 1} ^{i} j[\gcd(i, j) - 1] - 1\right)\\ \sum_{d = 1} ^{n} f(d, d) \sum_{i = 1} ^{\frac{n}{d}} i ^ 2 \phi(i)\\ g(n) = \sum_{i = 1} ^{n} i ^ 2 \times \phi(i)\\ i=1∑n​j=1∑n​f(i,j)d=1∑n​f(d,d)i=1∑dn​​j=1∑dn​​ij[gcd(i,j)=1]d=1∑n​f(d,d)⎝⎛​i=1∑dn​​ij=1∑i​j[gcd(i,j)−1]−1⎠⎞​d=1∑n​f(d,d)i=1∑dn​​i2ϕ(i)g(n)=i=1∑n​i2×ϕ(i)
容易发现 g ( n ) g(n) g(n)可以线性筛得到,所以我们只要动态维护 f ( d , d ) f(d, d) f(d,d)的前缀和即可,考虑用分块维护前缀和,满足 n \sqrt n n ​修改, O ( 1 ) O(1) O(1)查询。

#include <bits/stdc++.h>

using namespace std;

const int N = 4e6 + 10, mod = 1e9 + 7;

int prime[N], phi[N], g[N], f[N], cnt, n, m;

int L[N], R[N], id[N], sum[N], lazy[N], block, blocks;

bool st[N];

inline int add(int x, int y) {
  return x + y < mod ? x + y : x + y - mod;
}

inline int sub(int x, int y) {
  return x >= y ? x - y : x - y + mod;
}

void init() {
  phi[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!st[i]) {
      prime[++cnt] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
      st[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
      phi[i * prime[j]] = phi[i] * (prime[j] - 1);
    }
  }
  for (int i = 1; i < N; i++) {
    g[i] = add(g[i - 1], 1ll * i * i % mod * phi[i] % mod);
    f[i] = 1ll * i * i % mod, sum[i] = add(sum[i - 1], f[i]);
  }
  block = sqrt(n);
  for (int i = 1; i <= n; i += block) {
    L[++blocks] = i, R[blocks] = min(i + block - 1, n);
    for (int j = L[blocks]; j <= R[blocks]; j++) {
      id[j] = blocks;
    }
  }
}

inline int query(int x) {
  return add(sum[x], lazy[id[x]]);
}

inline void update(int x, int v) {
  int pos = id[x];
  for (int i = x; i <= R[pos]; i++) {
    sum[i] = add(sum[i], v);
  }
  pos++;
  while (pos <= blocks) {
    lazy[pos] = add(lazy[pos], v);
    pos++;
  }
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  scanf("%d %d", &m, &n);
  init();
  for (int cas = 1, a, b, k; cas <= m; cas++) {
    long long x;
    scanf("%d %d %lld %d", &a, &b, &x, &k);
    int p = __gcd(a, b);
    update(p, sub(0, f[p]));
    f[p] = (x / (a / p)) / (b / p) % mod;
    update(p, f[p]);
    int ans = 0;
    for (int l = 1, r; l <= k; l = r + 1) {
      r = k / (k / l);
      ans = add(ans, 1ll * g[k / l] * sub(query(r), query(l - 1)) % mod);
    }
    printf("%d\n", ans);
  }
  return 0;
}
上一篇:源码解读---mem2reg源码(3)


下一篇:easy_RSA