[Cqoi 2017] bzoj4815 小Q的表格 [莫比烏斯反演]

Description:

自己看題。

Solution:

這個 f f 的形式和gcdgcd很像，事實上每次修改 (a,b) ( a , b ) 會影響到 gcd(i,j)==gcd(a,b) g c d ( i , j ) == g c d ( a , b ) 。

是以我們隻用保留 gcd(i,i) g c d ( i , i ) 即可。每次修改 (a,b) ( a , b ) 等價于修改 gcd(a,b) g c d ( a , b ) 。

然後維護 S(d) S ( d ) ，表示 f(d,d) f ( d , d ) 的字首和。

那麼得出答案即是

∑ki=1f(i)S([ki]) ∑ i = 1 k f ( i ) S ( [ k i ] )

S(n)=∑ni=1ϕ(i)∗i2 S ( n ) = ∑ i = 1 n ϕ ( i ) ∗ i 2

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn =  + , P =  + ;
int n, m;
int mark[maxn], p[maxn], l[maxn], r[maxn], b[maxn];
ll phi[maxn], s[maxn], S[maxn], add[maxn], a[maxn];
int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}
ll power(ll x, ll t) {
    ll ret = ;
    for(; t; t >>= , x = x * x % P) {
        if(t & ) {
            ret = ret * x % P;
        }
    }
    return ret;
}
void ini() {
    phi[] = ;
    for(int i = ; i < maxn; ++i) {
        if(!mark[i]) {
            p[++p[]] = i;
            phi[i] = i - ;
        }
        for(int j = ; j <= p[] && i * p[j] < maxn; ++j) {
            mark[i * p[j]] = ;
            if(i % p[j] == ) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            phi[i * p[j]] = phi[i] * phi[p[j]];
        }
    }
    for(int i = ; i < maxn; ++i) {
        s[i] = (s[i - ] + phi[i] * i % P * i % P) % P;
    }
}
int main() {
    ini();
    scanf("%d%d", &m, &n);
    int B = sqrt(n);
    for(int i = ; i <= n; ++i) {
        S[i] = (S[i - ] + (long long) i * i % P) % P;
        a[i] = (long long) i * i % P;
        b[i] = (i - ) / B + ;
        if(!l[b[i]]) {
            l[b[i]] = i;
        }
        r[b[i]] = i;
    }
    while(m--) {
        int A, B, k;
        ll x, ans = ;
        scanf("%d%d%lld%d", &A, &B, &x, &k);
        int d = gcd(A, B);
        x %= P;
        x = x * d % P * d % P * power((long long) A * B % P, P - ) % P;
        for(int i = d; i <= r[b[d]]; ++i) {
            S[i] = (S[i] + x - a[d] + P) % P;
        }
        for(int i = b[d] + ; i <= b[n]; ++i) {
            add[i] = (add[i] + x - a[d] + P) % P;
        }
        a[d] = x;
        for(int i = , j; i <= k; i = j + ) {
            j = k / (k / i);
            ans = (ans + (S[j] + add[b[j]] - S[i - ] - add[b[i - ]] +  * P) % P * s[k / i] % P) % P;
        }
        printf("%lld\n", ans);
    }       
    return ;
}