数论网课习题解答

· · 个人记录

数论网课习题解答

前言

数论杀我。

有些题是之前做过的，那就直接口胡式子了。

在题目中可能会用 n 代替 min(n,m) 以缩减打字量。

因为有一定莫反基础，所以我不会再题解里面说很多怎么交换顺序、提什么东西出来，这些应该看得出来吧。

P2303 [SDOI2012] Longge 的问题

问题是求 \sum\limits_{i=1}^n(i,n)。(i,n) 一定是 n 的因子，所以我们考虑枚举 n 的所有因子 d，求有多少组 (i,n) 等于 d，也就是：

\sum_{d|n}d\sum_{i=1}^n[(d,i)=d]=\sum_{d|n}d\sum_{i=1}^{n/d}[(d,i)=1]=\sum_{d|n}d\varphi(n/d)

直接暴力搞能 AC。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

int phi(int x) {
    int res = x;
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) res = res / i * (i - 1);
        while(x % i == 0) x /= i;
    }
    if(x > 1) res = res / x * (x - 1);
    return res;
}

int n;

signed main() {
    n = get();
    int ans = 0;
    for(int i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            if(i * i != n) ans += i * phi(n / i) + n / i * phi(i);
            else ans += i * phi(i);
        }
    }
    cout << ans << endl;
    return 0;
}

P2257 YY的GCD

\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)\in P]\\ =&\sum_{p\in P}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]\\ =&\sum_{p\in P}\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}[gcd(i,j)=1]\\ =&\sum_{p\in P}\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}\sum_{d|i,d|j}\mu(d)\\ =&\sum_{p\in P}\sum_{d=1}^{n/p}\mu(d)\lfloor n/dp\rfloor\lfloor m/dp\rfloor\\ \end{aligned}

设 T=dp，原式改写为：

\begin{aligned} \sum_{T=1}^n\lfloor n/T\rfloor\lfloor m/T\rfloor\sum_{p\in P|T}\mu(T/p) \end{aligned}

预处理后面那个式子（复杂度接近于线性但貌似实际上不是，反正能过就对了），整除分块。

这道题用到了一个经典套路：设 T=dp。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int N = 1e7 + 5, MaxN = 1e7;
int pri[N], mu[N], vis[N], tot, sum[N];

void get_mu() {
    mu[1] = 1;
    for(register int i = 2; i <= MaxN; i++) {
        if(!vis[i]) mu[i] = -1, pri[++tot] = i;
        for(register int j = 1; j <= tot && i * pri[j] <= MaxN; j++) {
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0) { mu[i * pri[j]] = 0; break; }
            mu[i * pri[j]] = -mu[i];
        }
    }
    for(register int i = 1; i <= tot; i++) 
        for(register int j = 1; pri[i] * j <= MaxN; j++) sum[pri[i] * j] += mu[j];
    for(register int i = 1; i <= MaxN; i++) sum[i] += sum[i - 1];
}

int solve(int n, int m) {
    int res = 0;
    for(register int i = 1, j; i <= min(n, m); i = j + 1) {
        j = min(n / (n / i), m / (m / i));
        res += (sum[j] - sum[i - 1]) * (n / i) * (m / i);
    }
    return res;
}

signed main() {
    get_mu();
    int T = get();
    while(T--) {
        int n = get(), m = get();
        printf("%lld\n", solve(n, m));
    }
    return 0;
}

P3327 [SDOI2015]约数个数和

Lemma

d(ij)=\sum_{x|i}\sum_{y|j}[x\perp y]

证明（口胡）

此证明启发自这篇文章

首先根据唯一分解定理，ij,i,j 都可以被表示成 \prod p_i^{\alpha_i} 的形式。

设 ij 有一个因子 k，不妨将每个质因子分开考虑，假设 k 中有因子 p^c，i 中有因子 p^a，j 中有因子 p^b，为了防止算重，我们强行令（注意下面 a 和 \alpha 的区别）：

可以发现不会出现同时在 i 和 j 中选择的情况，换言之我们可以在 i,j 中枚举两个互质的因子 x,y 将它们所对应的 p^c 乘起来从而不重不漏地得到所有的 k。如果用抽象化的语言写下来就得到了上面的式子。

下面就可以开始推式子了。

\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^md(ij)\\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[(x,y)=1]\\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|x,d|y}\mu(d)\\ =&\sum_{x=1}^n\sum_{y=1}^m\lfloor n/x\rfloor\lfloor m/y\rfloor\sum_{d|x,d|y}\mu(d)\\ =&\sum_{d=1}^n\mu(d)\sum_{d|x}^n\sum_{d|y}^m\lfloor n/x\rfloor\lfloor m/y\rfloor\\ =&\sum\mu(d)\sum_{x=1}^{n/d}\sum_{y=1}^{m/d}\lfloor n/xd\rfloor\lfloor m/yd\rfloor\\ =&\sum\mu(d)(\sum_{x=1}^{n/d}\lfloor n/dx\rfloor)(\sum_{y=1}^{m/d}\lfloor m/dy\rfloor) \end{aligned}

发现后面两项实际上就是 d(x) 的前缀和，线筛预处理，整除分块求和即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int N = 1e5 + 5, MaxN = 1e5;
int mu[N], d[N], pri[N], tot, num[N], vis[N];

void seive() {
    mu[1] = d[1] = 1;
    for(int i = 2; i <= MaxN; i++) {
        if(!vis[i]) pri[++tot] = i, d[i] = 2, mu[i] = -1, num[i] = 1;
        for(int j = 1; j <= tot && i * pri[j] <= MaxN; j++) {
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0) {
                num[i * pri[j]] = num[i] + 1;
                d[i * pri[j]] = d[i]/ num[i * pri[j]]  * (num[i * pri[j]] + 1);
                mu[i * pri[j]] = 0;
                break;
            }
            num[i * pri[j]] = 1;
            d[i * pri[j]] = d[i] * 2;
            mu[i * pri[j]] = -mu[i];
        }
        mu[i] += mu[i - 1], d[i] += d[i - 1];
    }
}

int solve(int n, int m) {
    int res = 0;
    for(int i = 1, j; i <= min(n, m); i = j + 1) {
        j = min(n / (n / i), m / (m / i));
        res += (mu[j] - mu[i - 1]) * d[n / i] * d[m / i];
    }
    return res;
}

signed main() {
    seive();
    int T = get();
    while(T--) {
        int n = get(), m = get();
        printf("%lld\n", solve(n, m));
    }
    return 0;
}

P4213 【模板】杜教筛（Sum）

详见杜教筛专题文章。

SP4168 SQFREE - Square-free integers

考虑容斥，用总量减去有平方因子的，考虑某一个平方因子的贡献，即：

n+\sum_{i=2}^{\sqrt n} \mathrm{sign}(i) \lfloor n/i^2\rfloor

其中，\mathrm{sign}(i) 表示容斥系数，我们考虑构造出一组系数：

不难发现，这个 \mathrm{sign}=\mu。这样就可以 O(T\sqrt n) 求解了，原则上应该用整除分块，但是不写也跑过去了，所以就懒得写了。

#include<stdio.h>

const int N = 1e7 + 5;
int vis[N], pri[N], tot, mu[N];

void init() {
    for(int i = 2; i < N; i++) {
        if(!vis[i]) pri[++tot] = i, mu[i] = -1;
        for(int j = 1; j <= tot && i * pri[j] < N; j++) {
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0) { mu[i * pri[j]] = 0; break; }
            mu[i * pri[j]] = -mu[i];
        }
    }
}

void solve() {
    long long n, ans = 0;
    scanf("%lld", &n);
    ans = n;
    for(long long i = 2; i * i <= n; i++) ans = ans + mu[i] * (n / (i * i));
    printf("%lld\n", ans);
}

int main() {
    init();
    int T;
    scanf("%d", &T);
    while(T--) solve(); 
    return 0;
}

P3312 [SDOI2014]数表

考虑没有 a 的限制，其实就是：

\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m\sigma_0(\gcd(i,j))\\ =&\sum_{p=1}^n\sigma_0(p)\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=p]\\ =&\sum_{p=1}^n\sigma_0(p)\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}\sum_{d|i,d|j}\mu(d)\\ =&\sum_{p=1}^n\sigma_0(p)\sum_{d=1}^{n/d}\mu(d)\lfloor n/dp\rfloor\lfloor m/dp\rfloor\\ =&\sum_{T=1}^n\lfloor n/T\rfloor\lfloor m/T\rfloor\sum_{d|T}\mu(T/d)\sigma_0(d) \end{aligned}

设 F(x)=\sum\limits_{d|x,d\leq a}\mu(x/d)\sigma_0(d)，我们需要动态维护这个函数值。

考虑将询问离线，每次对于一个可能对当前 a 产生贡献的 d，枚举其倍数，更新 F(xd)，由于需要整除分块，搞个树状数组来维护就行了。

#define int long long
using namespace std;

int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int N = 1e5 + 5, P = 1ll << 31;
struct Query {
    int n, m, a, id;
    bool operator <(Query b) const { return a < b.a; }
} q[N];
struct Sigma {
    int d, x;
    Sigma() {}
    Sigma(int a, int b) { d = a, x = b; }
    bool operator <(Sigma b) const { return d < b.d; }
} bin[N];
int Q, top, pri[N], tot, vis[N], mu[N], d[N], g[N], ans[N];
namespace BIT {
    int sum[N];
    int lowbit(int x) { return x & -x; }
    void add(int x, int v) { while(x < N) sum[x] = (sum[x] + v) % P, x += lowbit(x); }
    int ask(int x) { int rs = 0; while(x) rs = (rs + sum[x]) % P, x -= lowbit(x); return rs; }
    int ask(int l, int r) { return (ask(r) - ask(l - 1) + P) % P; }
}
using namespace BIT;

void init() {
    mu[1] = d[1] = g[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!vis[i]) pri[++tot] = i, mu[i] = -1, d[i] = g[i] = i + 1;
        for(int j = 1; j <= tot && i * pri[j] < N; j++) {
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0) { 
                mu[i * pri[j]] = 0, g[i * pri[j]] = g[i] * pri[j] + 1, d[i * pri[j]] = d[i] / g[i] * g[i * pri[j]]; 
                break; 
            }
            mu[i * pri[j]] = -mu[i], g[i * pri[j]] = pri[j] + 1, d[i * pri[j]] = d[i] * g[i * pri[j]];
        }
    }
    for(int i = 1; i < N; i++) bin[++top] = Sigma(d[i], i);
    sort(bin + 1, bin + 1 + top);
}

void insert(int _d, int _x) {
    for(int i = 1; i * _x < N; i++) 
        add(i * _x, _d * mu[i]);
}

int solve(int n, int m) {
    int res = 0;
    for(int i = 1, r; i <= min(n, m); i = r + 1) {
        r = min(n / (n / i), m / (m / i));
        res = (res + (n / i) * (m / i) % P * ask(i, r) % P) % P;
    }
    return (res + P) % P;
}

signed main() {
    Q = get();
    for(int i = 1; i <= Q; i++) q[i].n = get(), q[i].m = get(), q[i].a = get(), q[i].id = i;
    sort(q + 1, q + 1 + Q);
    init();
    int maxr = 0;
    for(int i = 1; i <= Q; i++) {
        while(maxr < top && bin[maxr + 1].d <= q[i].a) 
            ++maxr, insert(bin[maxr].d, bin[maxr].x);
        ans[q[i].id] = solve(q[i].n, q[i].m);
    }
    for(int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
    return 0;
}

P1829 [国家集训队]Crash的数字表格 / JZPTAB

忘了怎么做了

P2480 [SDOI2010]古代猪文

数论全家桶。

首先有要算的东西在指数上，用欧拉定理，记得特判不互质。

肯定得用卢卡斯，但是模数巨大，显然不行，所以考虑将其质因数分解然后 CRT。

别的东西就没啥说的必要了。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int P = 999911659, N = 114514, Phi = P - 1, p[] = {0, 2, 3, 4679, 35617};
int n, g, ans[5], fac[N], res;

int qpow(int x, int y, int mod) {
    int res = 1;
    while(y) {
        if(y & 1) res = res * x % mod;
        x = x * x % mod, y >>= 1;
    }
    return res;
}
int inv(int x, int mod) { if(!x) return 1; return qpow(x, mod - 2, mod); }
void GetFac(int mod) { fac[0] = 1; for(int i = 1; i <= mod; i++) fac[i] = fac[i - 1] * i % mod; }
int C(int x, int y, int mod) {
    if(x < y) return 0;
    return fac[x] * inv(fac[y], mod) % mod * inv(fac[x - y], mod) % mod;
}
int Lucas(int x, int y, int mod) {
    if(x < y) return 0;
    if(!x) return 1;
    return Lucas(x / mod, y / mod, mod) * C(x % mod, y % mod, mod) % mod;
}
void CRT() { 
    for(int i = 1; i <= 4; i++) 
        res = (res + ans[i] * (Phi / p[i]) % Phi * inv(Phi / p[i], p[i]) % Phi) % Phi; 
}

signed main() {
    n = get(), g = get();
    if(g % P == 0) return printf("0\n"), 0;
    for(int t = 1; t <= 4; t++) {
        GetFac(p[t]); 
        for(int i = 1; i * i <= n; i++) {
            if(n % i) continue;
            ans[t] = (ans[t] + Lucas(n, i, p[t])) % p[t];
            if(i * i != n) ans[t] = (ans[t] + Lucas(n, n / i, p[t])) % p[t];
        }
    }
    CRT();
    printf("%lld\n", qpow(g, res, P));
    return 0;
}

P3768 简单的数学题

详见杜教筛专题。

P1587 [NOI2016]循环之美

Lemma

题目条件等价于求：

\sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k]

证明

暂时不会。

所以就直接开始推式子了（

\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k]\\ =&\sum_{j=1}^m[j\perp k]\sum_{i=1}^n\sum_{d|i,d|j}\mu(d)\\ =&\sum_{d=1}^n\mu(d)\sum_{d|i}\sum_{d|j}[j\perp k]\\ =&\sum_{d=1}^n\mu(d)[d\perp k]\lfloor n/d\rfloor\sum_{j=1}^{m/d}[j\perp k] \end{aligned}

解释下最后一步：把原来的 j 拆成 d 和 j/d 两部分分开算，必须两边全部互质才行。

如果我们能求出以下两个函数的前缀和，就可以对其进行整除分块：

F(x)=\sum_{i=1}^x[i\perp k] S(x)=\sum_{i=1}^x\mu(i)[i\perp k]

显然求 F 非常简单，k 将 x 分成了若干段，每段情况相似，而 k 非常小，直接预处理 0 到 k 的答案 f(x)，那么有：

F(x)=\lfloor x/k \rfloor f(k)+f(x\bmod k)

问题在于这个 S(x)，我们来推一波式子：

\begin{aligned} S(x)=&\sum_{i=1}^x\mu(i)[d\perp k]\\ =&\sum_{i=1}^x\mu(i)\sum_{d|i,d|k}\mu(d)\\ =&\sum_{d|k}\mu(d)\sum_{i=1}^{x/d}\mu(id) \end{aligned}

如果 i,d 不互质，显然 id 存在平方因子，\mu(id)=0，根据莫比乌斯函数的积性性，将式子改写为：

\begin{aligned} S(x)=&\sum_{d|k}\mu(d)\sum_{i=1}^{x/d}[i\perp d]\mu(i)\mu(d)\\ =&\sum_{d|k}\mu^2(d)\sum_{i=1}^{x/d}[i\perp d]\mu(i) \end{aligned}

发现后面那东西有点眼熟，它长得很像 S(x)。那么我们定义：

S(x,y)=\sum_{i=1}^x\mu(i)[i\perp y]

那么有：

S(x,y)=\sum_{d|y}\mu^2(d)S(x/d,d)

这样子就可以递归下去，记忆化搜索求解了。边界情况是 y=1，而显然这时候 [i\perp y] 恒成立，就变成了莫比乌斯函数的前缀和，直接杜教筛。

复杂度算起来非常迷惑，总之能过就是了。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int N = 5e6 + 5, K = 2005;
int n, m, _k; 
int f[N];
int vis[N], pri[N], tot, mu[N], smu[N];
map<pair<int, int>, int> mem;

int gcd(int x, int y) { return y? gcd(y, x % y) : x; }

void init() {
    mu[1] = 1, smu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!vis[i]) pri[++tot] = i, mu[i] = -1;
        for(int j = 1; j <= tot && i * pri[j] < N; j++) {
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
            mu[i * pri[j]] = -mu[i];
        }
        smu[i] = smu[i - 1] + mu[i];
    }
    for(int i = 1; i <= _k; i++) f[i] = f[i - 1] + (gcd(i, _k) == 1);
}

int F(int x) {
    return f[_k] * (x / _k) + f[x % _k];
}

int S(int x, int k) {
    if((k == 1 && x <= N) || (!x)) return smu[x];
    if(mem[make_pair(x, k)]) return mem[make_pair(x, k)];
    int res = 0;
    if(k == 1) {
        res=1;
        for(int i = 2, j; i <= x; i = j + 1) {
            j = x / (x / i);
            res -= (j - i + 1) * S(x / i, 1);
        }
    }
    else {
        for(int d = 1; d * d <= k; ++d) {
            if(k % d) continue;
            if(mu[d]) res += S(x / d, d);
            if(d * d != k && mu[k / d]) res += S(x / (k / d), k / d);
        }
    }
    return (mem[make_pair(x, k)] = res);
}

signed main() {
    n = get(), m = get(), _k = get();
    init();
    int lst = 0, ans = 0, now;
    for(int i = 1, j; i <= min(n, m); i = j + 1) {
        j = min(n / (n / i), m / (m / i));
        now = S(j, _k);
        ans += (now - lst) * (n / i) * F(m / i);
        lst = now;
    }
    printf("%lld\n", ans);
    return 0;
}

P4619 [SDOI2018]旧试题

暂时不会。