寒假集训Week1

狄利克雷卷积

CF757E

很巧妙，可以很明显发现：

\[f_{r+1}(n)=\sum_{d\mid n} f_r(n) \]

而

\[f_0(n)=2^{\Omega(n)} \]

则\(f\)函数的值与质因数的确切值无关。而发现 \(f\) 为积性函数。那么可以对于每一个质因数，和他分别的指数，预处理出形如 \(f_r(p^q)\) 的形式的函数值，再分解质因数计算即可。
代码：

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int R = 1e6 + 5;
const int LG = 22;
const int Md = 1e9 + 7;
ll ans[R][LG];
int lp[R];
vector<int> prim;
void init(void) {
    ans[0][0] = 1;
    for (int i = 1; i <= LG; ++i) 
        ans[0][i] = 2;
    for (int i = 1; i < R; ++i) {
        ans[i][0] = 1;
        for (int j = 1; j < LG; ++j) 
            ans[i][j] = (ans[i][j - 1] + ans[i - 1][j]) % Md;
    }
}
void get_primes(void) {
    for (int i = 2; i < R; ++i) {
        if (!lp[i]) {
            lp[i] = i;
            prim.push_back(i);
        }
        for (auto p : prim) {
            if (i * p >= R) break;
            lp[i * p] = p;
            if (i % p == 0) break;
        }
    }
}
int main() {
    FASTIO;
    init();
    get_primes();
    int q;
    cin >> q;
    while (q--) {
        int n, r;
        cin >> r >> n;
        ll ret = 1;
        while (true) {
            if (n == 1) break;
            int cnt = 0, lpp = lp[n];
            while (n % lpp == 0) {
                n /= lpp;
                ++cnt;
            }
            ret = (ret * ans[r][cnt]) % Md;
        }
        cout << ret << '\n';
    }
    return 0;
}

莫比乌斯反演

LG P1829

Link
恶心的推式子！！！

\[\begin{aligned}\sum_{i=1}^{n}\sum_{j=1}^{m} lcm(i,j) &=\sum_{d=1}^{\min(n,m)} \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{d}[\gcd(i,j)=d] \\ &=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} ij[ \gcd(i,j)=1] \\ &=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} j[ \gcd(i,j)=1] \\ &=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} j \times \epsilon(\gcd(i,j)) \\ &=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} j \sum_{x \mid \gcd(i,j)}\mu(x) \\ &=\sum_{d=1}^{\min(n,m)}d\sum_{x=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(x)\sum_{i=1}^{\lfloor \frac{n}{dx} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{dx} \rfloor} j \\ \end{aligned} \]

然后就可以套两层整除分块做了。
代码：

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e7 + 5;
const int Md = 20101009;
#define int ll
vector<int> prime;
int a, b, d;
int lp[N], miu[N], sum[N];
ll rev = (Md + 1) / 2;
ll get(int n, int m) {
    return n * (n + 1) % Md * rev % Md * m % Md * (m + 1) % Md * rev % Md;
}
ll calc(int n, int m) {
    if (n > m) swap(n, m);
    int l = 1, r = 0, ans = 0;
    for (; l <= min(n, m); l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += (sum[r] - sum[l - 1]) * get(n / l, m / l) % Md;
        ans += Md;
        ans %= Md;
    }
    return ans;
}
ll calc1(int n, int m) {
    if (n > m) swap(n, m);
    int l = 1, r = 0, ans = 0;
    for (; l <= min(n, m); l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += (l + r) * rev % Md * (r - l + 1) % Md * calc(n / l, m / l) % Md;
        ans += Md;
        ans %= Md;
    }
    return ans;
}
void get(void) {
    miu[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!lp[i]) {
            lp[i] = i;
            miu[i] = -1;
            prime.push_back(i);
        }
        for (auto p : prime) {
            if (i * p >= N) break;
            lp[i * p] = p;
            if (i % p == 0) {
                miu[i * p] = 0;
                break;
            }
            else
                miu[i * p] = -miu[i];
        }
    }
    for (int i = 1; i < N; ++i)
        sum[i] = (sum[i - 1] + miu[i] * i % Md * i % Md + Md) % Md;
}
signed main() {
    FASTIO;
    get();
    int n, m;
    cin >> n >> m;
    cout << calc1(n, m) << '\n';
    return 0;
}

LG P3327

Link
又是推式子。

\[\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m} \tau_0(ij)&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{u\mid i}\sum_{v\mid j}[\gcd(u,v)=1]\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{u\mid i}\sum_{v\mid j}\epsilon(\gcd(u,v))\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{u\mid i}\sum_{v\mid j}\sum_{x\mid \gcd(u,v)} \mu(x)\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid \gcd(i,j)}\mu(d)\tau_0(\frac{i}{d})\tau_0(\frac{j}{d})\\ &=\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\tau_0(i)\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\tau_0(j) \end{aligned} \]

代码：

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 5e4 + 5;
#define int ll
int lp[N], miu[N], d[N], lpp[N], cnt[N], sum[N], sum1[N];
vector<int> prim;
void get(void) {
    d[1] = 1;
    miu[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!lp[i]) {
            lp[i] = i;
            miu[i] = -1;
            d[i] = 2;
            lpp[i] = i;
            cnt[i] = 1;
            prim.emplace_back(i);
        }
        for (auto p : prim) {
            if (i * p >= N) break;
            lp[i * p] = p;
            if (i % p == 0) {
                lpp[i * p] = lpp[i] * p;
                cnt[i * p] = cnt[i] + 1;
                d[i * p] = d[i / lpp[i]] * (cnt[i] + 2);
                miu[i * p] = 0;
                break;
            }
            else {
                miu[i * p] = -miu[i];
                lpp[i * p] = p;
                cnt[i * p] = 1;
                d[i * p] = d[i] * 2;
            }
        }
    }
    for (int i = 1; i < N; ++i)
        sum[i] = sum[i - 1] + d[i];
    for (int i = 1; i < N; ++i)
        sum1[i] = sum1[i - 1] + miu[i];
}
int calc(int n, int m) {
    if (n > m) swap(n, m);
    int l = 1, r, ans = 0;
    for (; l <= min(n, m); l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += (sum1[r] - sum1[l - 1]) * sum[n / l] * sum[m / l];
    }
    return ans;
}
void solve(void) {
    int n, m;
    cin >> n >> m;
    cout << calc(n, m) << '\n';
}
signed main() {
    FASTIO;
    get();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

LG P2257

Link
推式子。

\[\begin{aligned} \sum_{p}\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=p] &=\sum_{p}\sum_{i=1}^{\lfloor \frac{n}{p} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{p} \rfloor}\epsilon(\gcd(i,j))\\ &=\sum_{p}\sum_{i=1}^{\lfloor \frac{n}{p} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{p} \rfloor}\sum_{d\mid \gcd(i,j)}\mu(d)\\ &=\sum_{p}\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor \frac{n}{pd} \rfloor\lfloor \frac{m}{pd} \rfloor\\ \end{aligned} \]

不妨令 \(T=pd\)，则：

\[\begin{aligned} 原式&=\sum_{T=1}^{\min(n,m)}\sum_{p}\mu(\frac{T}{p})\lfloor\frac{n}{T} \rfloor \lfloor\frac{m}{T} \rfloor\\ &=\sum_{T=1}^{\min(n,m)}\lfloor\frac{n}{T} \rfloor \lfloor\frac{m}{T} \rfloor \sum_{p\mid T} \mu(\frac{T}{p}) \end{aligned}\]

可以直接处理。
代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
LL mu[10000010];int flag[10000010],prime[10000010],cnt,f[10000010],sum[10000010];
void sieve() {
    mu[1]=1;
    for (int i=2;i<=10000000;i++) {
        if (!flag[i]) prime[++cnt]=i,mu[i]=-1;
        for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
            flag[i*prime[j]]=1;
            if (i%prime[j]==0) break;
            mu[i*prime[j]]=-mu[i];
        }
    }
    for (int i=1;i<=cnt;i++)
        for (int j=1;prime[i]*j<=10000000;j++)
            f[j*prime[i]]+=mu[j];
    for (int i=1;i<=10000000;i++)
        sum[i]=sum[i-1]+f[i];
}
LL solve(int a,int b) {
    LL ans=0;
    if (a>b) swap(a,b);
    for (int l=1,r=0;l<=a;l=r+1) {
        r=min(a/(a/l),b/(b/l));
        ans+=(LL)(sum[r]-sum[l-1])*(LL)(a/l)*(LL)(b/l);
    }
    return ans;
}
int main() {
    sieve();
    int n,m,T;scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        if (n>m) swap(n,m);
        printf("%lld\n",solve(n,m));
    }
}

AGC038 C

Link
挺简单，可以发现原式其实是求的一个三角和（不包括对角线），则可以用整体减对角线再除2即可。
推式子。。。

\[\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}lcm(a_i,a_j)&=\sum_{d=1}^{V}\sum_{i=1}^n\sum_{j=1}^n\frac{a_ia_j}{\gcd(a_i,a_j)}\\ &=\sum_{d=1}^{V}\sum_{i=1}^{\lfloor\frac{V}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{V}{d}\rfloor}cnt_{id}cnt_{jd}ijd[\gcd(i,j)=1]\\ &=\sum_{d=1}^{V}\sum_{x\mid d}\mu(x)\sum_{i=1}^{\lfloor\frac{V}{dx}\rfloor}\sum_{j=1}^{\lfloor\frac{V}{dx}\rfloor}cnt_{idx}cnt_{jdx}ijx^2d\\ &=\sum_{T=1}^{V}\sum_{d\mid T}\mu(d)\times \frac{T^2}{d}(\sum_{i=1}^{\lfloor \frac{V}{T} \rfloor}cnt_{iT} \times i)^2 \end{aligned} \]

然后就结束了。
代码：

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
#define int ll
using pii = pair<int, int>;
const int N = 2e5 + 5;
const int V = 1e6 + 5;
const int Md = 998244353;
int miu[V], lp[V], a[N], n, sum[V], cnt[V];
vector<int> prime;
void get(void) {
    miu[1] = 1;
    for (int i = 2; i < V; ++i) {
        if (!lp[i]) {
            prime.push_back(i);
            miu[i] = -1; 
        }
        for (auto p : prime) {
            if (i * p >= V) break;
            lp[i * p] = p;
            if (i % p == 0) {
                miu[i * p] = 0;
                break;
            }
            miu[i * p] = -miu[i];
        }
    }
    for (int d = 1; d < V; ++d) {
        for (int T = d; T < V; T += d) {
            (sum[T] += (1ll * miu[T / d] * T * T / d % Md + Md) % Md) %= Md;
        }
    }
}
const int rev = (Md + 1) / 2;
signed main() {
    FASTIO;
    get();
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], ans = (ans - a[i] + Md) % Md;
    for (int i = 1; i <= n; ++i) 
        cnt[a[i]] ++;
    for (int T = 1; T < V; ++T) {
        int ret = 0;
        for (int i = 1; i * T < V; ++i) {
            (ret += (cnt[i * T] * i % Md) % Md) %= Md;
        }
        ans = (ans + (ret * ret % Md * sum[T] % Md + Md) % Md) % Md;
    }
    ans = (ans * rev % Md) % Md;
    cout << ans << '\n';
    return 0;
}

HDU 4746

Link
非常好的一道题，反正不是板子。
推式子。

\[\begin{aligned} \sum_{i=1}^n \sum_{j=1}^m [f(\gcd(i,j))\le P]&=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor }\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor } [f(d)\le p] [\gcd(i,j)=1]\\ &=\sum_{d=1}^{\min(n,m)} [f(d)\le p]\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor }\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor } [\gcd(i,j)=1]\\ &=\sum_{d=1}^{\min(n,m)}[f(d)\le p] \sum_{k=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)} \mu(k)\lfloor \frac{n}{dk} \rfloor\lfloor \frac{m}{dk} \rfloor\\ &=\sum_{T=1}^{\min(n,m)}\lfloor \frac{n}{T} \rfloor\lfloor \frac{m}{T} \rfloor \sum_{d \mid T}\mu(\frac{T}{d})[f(d)\le p] \end{aligned} \]

然后非常妙，先把询问离线，按照 \(p\) 从小到大排序。随着 \(p\) 的增加，可以用调和级数进行更新。
此处用树状数组维护系数和，再套整除分块即可。
代码：

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 5e5 + 5;
const int V = 5e5 + 1;
#define int ll
int lp[N], f[N], miu[N], ans[N];
vector<int> prime, ds[N];
struct node {
    int n, m, p, id;
    bool operator < (const node &o) const {
        return p < o.p;
    }
}query[N];
struct BIT {
#define lowbit(x) (x & -x)
    int tree[N];
    void update(int pos, int val) {
        for (; pos < N; pos += lowbit(pos))
            tree[pos] += val;
    }
    int query(int pos) {
        if (!pos) return 0;
        int ret = 0;
        for (; pos; pos -= lowbit(pos))
            ret += tree[pos];
        return ret;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
#undef lowbit
}T;
void get(void) {
    f[1] = 0;
    miu[1] = 1;
    for (int i = 2; i < V; ++i) {
        if (!lp[i]) {
            f[i] = 1;
            miu[i] = -1;
            prime.push_back(i);
        }
        for (auto p : prime) {
            if (i * p >= V) break;
            f[i * p] = f[i] + 1;
            lp[i * p] = p;
            if (i % p == 0) {
                miu[i * p] = 0;
                break;
            }
            miu[i * p] = -miu[i];
        }
    }
    for (int i = 1; i < V; ++i) 
        ds[f[i]].push_back(i);
}
signed main() {
    FASTIO;
    get();
    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        cin >> query[i].n >> query[i].m >> query[i].p;
        query[i].id = i;
        if (query[i].n > query[i].m) swap(query[i].n, query[i].m);
    }
    query[0].p = -1;
    sort(query + 1, query + t + 1);
    for (int i = 1; i <= t; ++i) {
        for (int j = query[i - 1].p + 1; j <= query[i].p; ++j) 
            for (auto d : ds[j]) 
                for (int k = d; k < V; k += d) 
                    T.update(k, miu[k / d]);
        int l = 1, r = 0;
        for (; l <= query[i].n; l = r + 1) {
            r = min((query[i].m / (query[i].m / l)), (query[i].n / (query[i].n / l)));
            ans[query[i].id] += (query[i].n / l) * (query[i].m / l) * T.query(l, r);
        }
    }
    for (int i = 1; i <= t; ++i)
        cout << ans[i] << '\n';
    return 0;
}

posted @ 2026-02-04 20:46 tanjiaqi 阅读(2) 评论(0) 收藏举报

刷新页面返回顶部

Tom-tanjiaqi