标签： 数学

高中数学学习笔记 – 椭圆

by woshiluo

我怎么也沦落到发这种文章了。

整理都整理完了，不发白不发。

1 定义

给定两点 $F_1, F_2$，令 $|F_1F_2| = 2c$，存在动点 $P$ 满足 $|PF_1| + |PF_2| = 2a(2a>2c)$，则 P 的轨迹曲线为椭圆。

$2a = 2c$ 时 P 的轨迹为线段，也就是线段 $F_1F_2$；
$2a < 2c$ 时 P 不存在。

  • $F_1, F_2$ 称为焦点。
Continue reading “高中数学学习笔记 – 椭圆”

Codeforces Round 1699 解题报告

by woshiluo

考试链接： https://codeforces.com/contest/1699

考试的时候 30min 写完 ABC 发现 D 没几个人就摸了。考完看了眼 E 发现一眼切。最后竟然上分了，我大受震撼。

A The Third Three Number Problem

求能否找到任意三个数字 $a,b,c$ 使得 $(a \oplus b) + (a \oplus c) + (b \oplus c) = n$ 。
容易发现奇数根本不可能，偶数随便构造。

B Almost Ternary Matrix

给表格染色。使得对于任意一个格子，有且只有两个相邻格子和这个颜色不同。
以 2x2 为一个单位，交叉构造即可。

Continue reading “Codeforces Round 1699 解题报告”

AtCoder Regular Contest 084 D Small Multiple

by woshiluo

题意

题目链接: https://atcoder.jp/contests/arc084/tasks/arc084_b

要求 $ x = ak(a \in N) $，定义 $f(x)$ 为 $x$ 在十进制下每一位数字的和

思路

一开始肯定想的是大力枚举，但是很快就可以发现大力枚举可以被卡掉，因为另一个数字可以非常大

然后就考虑缩小另一个数字的范围

一开始的思路顺着质因数分解走的，但是想了半天没有想出来

考后发现顺着质因数的过于复杂，我们可以直接考虑 $x \bmod k$ 意义下的情况

从 $ x $ 到 $ x + 1 $，答案显然增加 1

但是如果 x 一直加 1 会加到 10 ，这个情况答案在事实上没有增加 1

我们可以发现只有其在某一步变成 10 倍才会发生这种事件，那么再加一条边

从 $x$ 到 $10x$，答案不增加

这样就构成了一条图，从 $0$ 到 $1$ 的最短路就是所求答案

Continue reading “AtCoder Regular Contest 084 D Small Multiple”

Codeforces Contest #1325 解题报告 & 题目大意

by woshiluo

A EhAb AnD gCd

题目大意

给定一个整数 $x（2\leq x \leq 10^9)$

求 $a,b$ 满足 $\gcd(a,b) + \operatorname{lcm}(a,b) = x$

多组解输出任意一个

Code

这有啥说的，随便找个质因数让后输出 $p, x$ 就可以

// Woshiluo Luo<[email protected]>
// 2020/03/14 22:36:48

#include <cmath>
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

int t, x;

int main() {
    scanf( "%d", &t );
    while( t -- ) {
        scanf( "%d", &x );
        int sq = std::sqrt(x) + 1;
        for( int i = 1; i <= sq; i ++ ) {
            if( x % i == 0 ) {
                int tmp = ( x / i ) - 1;
                if( tmp == 0 )
                    continue;
                printf( "%d %d\n", i, tmp * i );
                break;
            }
        }
    }
}

B CopyCopyCopyCopyCopy

题目大意

给你一个长度为 $n$ 的数列 $a$, 现在你可以复制无数个 $a$ 接到原来的数列后面

问这样接完后，最长严格上升子序列的长度

Code

因为可以接无限次，所以直接输出数字个数就可以了

// Woshiluo Luo<[email protected]>
// 2020/03/14 22:42:47
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e5 + 1e4;

int t;
int n;
int a[N];

int main() {
    scanf( "%d", &t );
    while( t -- ) {
        scanf( "%d", &n );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%d", &a[i] );
        }
        std::sort( a + 1, a + n + 1 );
        int cnt = 0, la = 0;
        for( int i = 1; i <= n; i ++ ) {
            if( i == 1 || a[i] != la ) {
                la = a[i];
                cnt ++;
            }
        }
        printf( "%d\n", cnt );
    }
}

C Ehab and Path-etic MEXs

题目大意

给一棵节点数为 $n$ 的树

现在你要给每条边一个边权，要求：

  • 边权为一个整数 $v(0\leq v \leq n – 2)$
  • 每条边的边权不能和别的边的相同

现在定义 $MEX(u,v)$ 为 $u,v$ 之间的最短简单路径上没有出现的边权中的最小值

请给出一种边权方案，最小化 $\max{MEX(u,v)}$

思路

考虑每条边会被算进去多少次，记为每条边的贡献

贡献越大给越大的边就可以了

实际上可以更加简化，因为无论如何一定有一个 $MEX \geq 2$

所以我们尽可能避免 $0,1,2$ 出现在一条边上即可

随便找一个度数 $\geq 2$ 的点，把这三个数字放上去即可

如果没有这种点，那么怎么摆都会有一条 $MEX=n-1$ 的路径

Code

// Woshiluo Luo<[email protected]>  
// 2020/03/14 22:52:18
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e5 + 1e4;

// Edge Start
struct edge {
    int to, next, val;
} e[ N << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to, int val ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    e[ecnt].val = val;
    ehead[now] = ecnt;
}
// Edge End

struct node { long long val; int id; } max[N];
bool cmp( node _a, node _b ) { return _a.val < _b.val; }

int n, x, y;
int son[N], val[N];

void dfs( int now, int la ) {
    son[now] = 1;
    for( int i = ehead[now]; i; i = e[i].next ) {
        if( e[i].to == la )
            continue;
        dfs( e[i].to, now );
        son[now] += son[ e[i].to ];
        max[ e[i].val ].val = ( 1LL * son[ e[i].to ] * ( n - son[ e[i].to ] ) );
    }
}

int main() {
#ifdef woshiluo
    freopen( "c.in", "r", stdin );
    freopen( "c.out", "w", stdout );
#endif
    scanf( "%d", &n );
    for( int i = 1, u, v; i < n; i ++ ) {
        max[i].id = i;
        scanf( "%d%d", &u, &v );
        add_edge( u, v, i );
        add_edge( v, u, i );
    }

    dfs( 1, 0 );

    std::sort( max + 1, max + n, cmp );

    for( int i = 1; i < n; i ++ ) {
        val[ max[i].id ] = i - 1;
    }

    for( int i = 1; i < n; i ++ ) {
        printf( "%d\n", val[i] );
    }
}

D Ehab the Xorcist

给定两个整数 $u,v$ 求最短的数列 $a$ 满足

  • $$ \sum a = v $$
  • xor 和为 $u$

多解输出任意一个

无解输出 $-1$

题目大意

这题感觉的 C 简单啊

满足 $xor$ 容易，满足 $v$ 的话需要难度

考虑最后 $xor$ 的结果受每个二进制位的和的奇偶性影响

因此可以确定每一位的奇偶性

然后随便搞一下满足 $v$ 就可以了

Code

// Woshiluo Luo<[email protected]>
// 2020/03/14 23:39:20
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

unsigned long long u, v;
int bit_u[110], bit_less[110], bit_cnt[110];
std::vector<unsigned long long> ans;

inline void noans() {
    printf( "-1\n" );
    exit(0);
}

void to_bit( unsigned long long a, int bit[] ) {
    int cnt = 0;
    while( a ) {
        bit[ ++ cnt ] = a & 1;
        a >>= 1;
    }
}

int main() {
    scanf( "%llu%llu", &u, &v );
    if( v < u )
        noans();

    to_bit( v - u, bit_less );
    to_bit( u, bit_u );

    for( int i = 1; i <= 100; i ++ ) {
        bit_cnt[i] = bit_u[i];
    }
    int p = 64;
    int cnt = 0;
    while( p ) {
        bit_cnt[p] += ( cnt - ( cnt & 1 ) );
        cnt = cnt & 1;
        if( bit_less[p] )
            cnt ++;
        p --; cnt <<= 1;
    }

    if( cnt != 0 )
        noans();

    bool flag = true;
    while( flag ) {
        flag = false;
        unsigned long long out = 0;
        unsigned long long p = 1;
        for( int i = 1; i <= 64; i ++, p <<= 1 ) {
            if( bit_cnt[i] ) {
                out = out | p;
                bit_cnt[i] --;
                flag = true;
            }
        }
        if( flag )
            ans.push_back(out);
    }

    cnt = ans.size();
    printf( "%d\n", cnt );
    for( int i = 0; i < cnt; i ++ ) {
        printf( "%llu ", ans[i] );
    }

}

E Ehab’s REAL Number Theory Problem

题目大意

给你一个长度为 $n$ 的数列，保证数列中每个数字有不超过 $7$ 个因数

请求出最短的子序列，使子序列成绩为完全平方数

思路

这题比 F 题难吧…

首先由 保证数列中每个数字有不超过 $7$ 个因数 得每个数不会有超过两个 $1$ 和其本身以外的质因数

然后我们可以先把每个数里的完全平方数因子先除掉，因为这些不会对答案造成影响

这样下来每个数的因子只有 1 和其本身以及两个质因数（前提是这个数不是质数）

然后建图，如果这个数是质数，将其和 $1$ 连接，如过不是将其的两个质因数连接

剩下就是求最小环

Code

// Woshiluo Luo<[email protected]>
// 2020/03/15 22:08:53

#include <cmath>
#include <cstdio>
#include <cstring>

#include <queue>
#include <vector>
#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e6 + 1e4;
const int M = 1100;
const int INF = 0x3f3f3f3f;

int n, ans = INF;
int dis[N], fa[N];
bool marked[N], pool[N];

// Edge Start
struct edge {
    int cur, to, next;
} e[ N << 1 ];
int ehead[N], ecnt = 1;
inline void add_edge( int now, int to ) {
    ecnt ++;
    e[ecnt].cur = now;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End

int bfs( int st ) {
    memset( dis, INF, sizeof(dis) );
    memset( fa, 0, sizeof(fa) );
    std::queue<int> q;
    q.push(st); dis[st] = 0;
    while( !q.empty() ) {
        int cur = q.front(); q.pop();
        for( int i = ehead[cur]; i; i = e[i].next ) {
            if( e[i].to == fa[cur] )
                continue;

            if( dis[ e[i].to ] >= INF ) {
                fa[ e[i].to ] = cur;
                dis[ e[i].to ] = dis[cur] + 1;
                q.push( e[i].to );
            }
            else {
                return dis[cur] + dis[ e[i].to ] + 1;
            }
        }
    }
    return INF;
}

int main() {
    scanf( "%d", &n );
    for( int i = 1, x; i <= n; i ++ ) {
        scanf( "%d", &x );
        std::vector<int> a;
        int cnt = std::sqrt(x) + 1;
        while(cnt > 1) {
            int cnt_pow = cnt * cnt;
            while( x % cnt_pow == 0 )
                x /= cnt_pow;
            cnt --;
        }
        if( x == 1 )
            chk_Min( ans, 1 );
        if( pool[x] )
            chk_Min( ans, 2 );
        pool[x] = true;
        int tmp = std::sqrt(x);
        for( int j = 2; j <= tmp; j ++ ) {
            if( x % j == 0 ) {
                a.push_back(j);
                a.push_back( x / j );
                break;
            }
        }
        if( a.size() == 0 ) {
            add_edge( 1, x );
            add_edge( x, 1 );
        }
        else if( a.size() != 0 ) {
            add_edge( a[0], a[1] );
            add_edge( a[1], a[0] );
        }
    }

    if( ans != INF ) {
        printf( "%d\n", ans );
        return 0;
    }

    for( int i = 1; i <= 1000; i ++ ) {
        if( ehead[i] )
            chk_Min( ans, bfs(i) );
    }

    if( ans >= INF )
        ans = -1;

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

F Ehab’s Last Theorem

题目大意

给定一个 $n$ 个节点的图

令 $glo=\lceil\sqrt{n}\rceil$

你要么找到一个长度和 $glo$ 相等的环

要么找到一个比 $glo$ 小的独立集

Code

先试图找环，找不到肯定有独立集

// Woshiluo Luo<[email protected]>  
// 2020/03/15 15:49:32
#include <cstdio>
#include <cstring>

#include <stack>
#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e5 + 1e4;
const int M = 2e5 + 1e4;

int n, m, need;

int dep[N];
bool vis[N];
std::stack<int> st;

// Edge Start
struct edge { int to, next; } e[ M << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End


void dfs( int now ) {
    st.push(now);
    dep[now] = st.size();
    for( int i = ehead[now]; i; i = e[i].next ) {
        if( dep[ e[i].to ] == 0 )
            dfs( e[i].to );
        else if( dep[now] - dep[ e[i].to ] + 1 >= need ) {
            int size = dep[now] - dep[ e[i].to ] + 1;
            printf( "%d\n%d\n", 2, size );
            for( int i = 1; i <= size; i ++ ) {
                printf( "%d ", st.top() );
                st.pop();
            }
            exit(0);
        }
    }
    if( !vis[now] ) {
        for( int i = ehead[now]; i; i = e[i].next ) {
            vis[ e[i].to ] = true;
        }
    }
    st.pop();
}

int main() {
#ifdef woshiluo
    freopen( "f.in", "r", stdin );
    freopen( "f.out", "w", stdout );
#endif
    scanf( "%d%d", &n, &m );
    while( need * need < n )
        need ++;

    while( m -- ) {
        int u, v;
        scanf( "%d%d", &u, &v );
        add_edge( u, v ); add_edge( v, u );
    }

    dfs(1);

    printf( "%d\n", 1 );
    int cnt = 0;
    for( int i = 1; i <= n; i ++ ) {
        if( vis[i] == false ) {
            printf( "%d ", i );
            cnt ++;
        }
        if( cnt == need )
            break;
    }
}

AGC 034 F RNG and XOR

by woshiluo

题目连接: https://atcoder.jp/contests/agc034/tasks/agc034_f

道理我都懂，可是不看题解不到啊……

$$\newcommand \xor{\mathbin{\mathbf{xor}}}$$

1 题意

给定一个数字 $n$

对于 $0 \cdots 2^n – 1$ 中每个数字都有一个 $a_i$

现在有一个数 $X$, 一开始为 $0$

每一次操作会随机选择一个数字 $i$ （其中 $0 \leq i \leq 2^n – 1$，选中 $i$ 的概率为 $\frac{a_i}{\sum a}$）

然后令 $X = X \oplus i$

问使 $X=i$ 的期望次数

2 思路

先令
$$p_i=\frac{a_i}{\sum a}$$

令 $f_i$ 表示从 $i$ 到 $0$ 的期望次数，这和从 $0$ 到 $i$ 显然是一样的

接着有一个非常显然的式子

$$
\begin{aligned}
f_i &= f_{i \xor j} \times p_j + 1 ( i \neq 0 )\\
f_i – 1 &= f_{i \xor j } \times p_j ( i \neq 0 )
\end{aligned}
$$

然后我们就可以得到这个式子

$$ (f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \oplus (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\
= ( x, f_1 – 1, f_2 – 1, \cdots, f_{2^{n-1}} – 1, f_{2^n-1} – 1 ) $$

但是 $x$ 是未知的

注意到 $\sum p = 1$ 所以左边右边的和是相等的

所以

$$
\begin{aligned}
x &= \sum_{i=0}^{2^n-1} f_i – \sum_{i=1}^{2^n-1} f_i – 1 \\
&= f_0 + 2^n – 1
\end{aligned}
$$

$$
(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \oplus (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\
= ( f_0 + 2^n – 1, f_1 – 1, f_2 – 1, \cdots, f_{2^{n-1}} – 1, f_{2^n-1} -1 )
$$

我们需要的使其中两个式子没有未知数

注意到如果使 $p_0 = p_0 – 1$

那么右边每一个数都会减去 $f_i$

即

$$
(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \oplus (p_0 – 1, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\ = ( 2^n – 1, – 1, – 1, \cdots, -1, -1 )
$$

于是就可以放进 FWT 里直接做

然后你就发现这东西跑出来是错的……

为什么呢

令

$$
\begin{aligned}
\mathbf{P} & = (p_0 – 1, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\
\mathbf{A} & = ( 2^n – 1, – 1, – 1, \cdots, -1, -1 )
\end{aligned}
$$

因为 $\mathbf{P}$ 和 $\mathbf{A}$ FWT 后第一位都是 $0$

没有办法倒推出来 $f_0$

但是可以发现 $f$ 的值是可以平移的

即

$$ f_i + k = \sum_{i=0}^{2^n-1} p_j(f_{i \oplus j} + k) + 1 = \sum_{i=0}^{2^n-1} f_{i \oplus j} \times p_j + k + 1 $$

那么我们又知道 $f_i = 0$

所以将 $f$ 每一位都减去 $f_0$ 即可

3 Code

#include <cstdio> 

const int N = 1 << 20;
const int mod = 998244353;

int n;
int a[N], b[N], p[N], sum;

inline i
nt add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline void add_eq( int &a, int b ) { a = ( a + b ) % mod; }
inline void mul_eq( int &a, int b ) { a = ( 1LL * a * b ) % mod; }

int ksm( int a, int p ) {
    int res = 1;
    while( p ) {
        if( p & 1 )
            res = mul( res, a );
        a = mul( a, a );
        p >>= 1;
    }
    return res;
}
inline int inv( int a ) { return ksm( a, mod - 2 ); }

void XOR( int *f, int len, int x = 1 ) {
    for( int o = 2, k = 1; o <= len; o <<= 1, k <<= 1 ) {
        for( int i = 0; i < len; i += o ) {
            for( int j = 0; j < k; j ++ ) {
                add_eq( f[ i + j ], f[ i + j + k ] );
                f[ i + j + k ] = add( f[ i + j ], add( - f[ i + j + k ], - f[ i + j + k ] ) );
                mul_eq( f[ i + j ], x ); mul_eq( f[ i + j + k ], x );
            }
        }
    }
}

int main() {
#ifdef woshiluo
    freopen( "F.in", "r", stdin );
    freopen( "F.out", "w", stdout );
#endif
    scanf( "%d", &n );
    n = 1 << n;
    for( int i = 0; i < n; i ++ ) {
        scanf( "%d", &a[i] );
        sum += a[i];
        b[i] = mod - 1;
    }
    sum = inv(sum);
    for( int i = 0; i < n; i ++ ) {
        p[i] = mul( a[i], sum );
    }

    b[0] = n - 1; p[0] -= 1;
    XOR( b, n ); XOR( p, n );
    for( int i = 0; i < n; i ++ ){
        mul_eq( b[i], inv( p[i] ) );
    }
    XOR( b, n, inv(2) );
    for( int i = 0; i < n; i ++ ) {
        printf( "%d\n", ( ( add( b[i], -b[0] ) + mod ) % mod ) );
    }
}

平面向量学习笔记（大概？）

by woshiluo

这篇文章咕了好久了，鬼知道为什么

本篇文章的目的只是为了更方便的学习 P2742 【模板】二维凸包 这道题目，如果有不详细或者错误之处，往各位大佬们多多指出

1 定义

向量：有大小，有方向 的量是向量，然而数学中研究的向量通常是 自由向量，即起点终点并不重要

向量的模：向量的长度被称为向量的模

零向量：模为 $0$ 的向量，零向量方向任意，记为 $\vec 0$ 或 $\mathbf 0$

单位向量：模为 $1$ 的向量是其在该方向的单位向量

Continue reading “平面向量学习笔记（大概？）”

中山纪念中学 Day 10 2019.08.10 解题报告 & 题解

by woshiluo

T1 数学题 Math

1 记录

真就数学题目呗

考场企图推正解，结果最后只推出了 60 分的，哭了

正解参见 欧几里得算法的应用.pdf

这是真的类欧几里得算法

Continue reading “中山纪念中学 Day 10 2019.08.10 解题报告 & 题解”

狄利克雷卷积 && 杜教筛 入门 — P4213 【模板】杜教筛（Sum）

by woshiluo

狄利克雷卷积

数论函数

数论函数是指一类函数，其定义域是正整数，值域是一个数集

积性函数都是数论函数

常见的数论函数有

  • $id(n) = n$ 单位函数，完全积性函数
  • $\epsilon(n) = [n = 1]$ 元函数，完全积性函数
  • $d(n)$ 约数个数，积性函数
  • $\sigma(n)$ 约数和函数，积性函数
  • $\mu(n)$ 莫比乌斯函数，积性函数
  • $\varphi(n)$ 欧拉函数，积性函数
Continue reading “狄利克雷卷积 && 杜教筛 入门 — P4213 【模板】杜教筛（Sum）”

莫比乌斯反演入门 – [SDOI2015]约数个数和

by woshiluo

道理我都懂，考试时这东西能推？

本人菜鸡，有问题请指出

鉴于不同博客对于整除符号$|$的定义不同， 特此表明本博客的整除定义

$a | b$ 表明 $b$ 是 $a$ 的倍数

0x01 什么是反演

对于一个数列${f_n}​$,如果有另外一个数列${g_n}​$满足如下条件
$$
g_n = \sum_{i = 1}^n a_if_i
$$
反演的过程是用$ g_n$来表示 $f_n$
$$
f_n = \sum_{i = 0}^n b_ig_i
$$

Continue reading “莫比乌斯反演入门 – [SDOI2015]约数个数和”