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

道理我都懂,考试时这东西能推?

本人菜鸡,有问题请指出

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

$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
$$

0x02 莫比乌斯函数

设$n = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \cdots \times p_k^{a_k}$ ,其中 $p$ 为质数,则定义如下
$$
\mu(n) =
\begin{cases} 1 & n = 1 \\
(-1) ^ m & \prod\limits_{i = 1} ^ {m} a_i = 1 \\
0 & \textrm{otherwise}(a_i \gt 1)
\end{cases}
$$

性质 1

$\mu​$ 函数是积性函数

没啥可以说的,线性筛就完事了

void get_pri(){
    vis[1] = 1; mu[1] = 1;
    for(int i = 2; i <= N; i++){
        if( vis[i] == false ){
            pri[ ++pcnt ] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= pcnt; j++){
            if( pri[j] * i > N ) 
                break;
            vis[ i * pri[j] ] = true;
            if( i % pri[j] == 0 ){
                mu[ pri[j] * i ] = 0;
                break;
            }
            else 
                mu[ pri[j] * i ] = -mu[i];    
        }
    }
}

性质 2

对于任意的非负整数
$$
\sum_{d|n}\mu(d)=
\begin{cases}
1 & n = 1\\
0 & n > 1
\end{cases}
$$

0x03 莫比乌斯反演

有两个数论函数$f(n)$和$g(n)$ ,且满足条件
$$
g(n) = \sum_{d|n}f(d)
$$
则一定存在
$$
f(n) = \sum_{d|n}\mu(d)g(\lfloor \frac{n}{d}\rfloor)
$$

证明

我们这里用性质证明QAQ
$$
\begin{align}
f(n) & = \sum_{d|n}\mu(d)g(\lfloor \frac{n}{d} \rfloor)\\
& = \sum_{d|n}\mu(d) \sum_{d’|\lfloor \frac{n}{d} \rfloor} f(d’)\\
& = \sum_{d|n} f(d) \sum_{d’|\lfloor \frac{n}{d} \rfloor} \mu(d’)\\
&= f(n)
\end{align}
$$

0x10 P3327 [SDOI2015]约数个数和

0x11 题目

题目链接: https://www.luogu.org/problemnew/show/P3327

题目需要让我们求 $\sum_{i=1}^n \sum_{j=1}^m d(i j)​$

其中$ d ​$为约数个数

显然$d(ij) = \sum_{x|i} \sum_{y|j} [gcd(x,y) = 1]​$

给一个比较感性的解释

显然,这个式子在枚举$i,j​$ 的所有约数的 gcd

如果 两个约数 gcd 为 1,则代表在 $i \cdot j$ 里可以有一个新的约数$x \cdot y$,否则表明这个已经被之前枚举过了

然后开始我们的魔法
$$
\sum_{i=1}^n \sum_{j=1}^m d(i j) \\
\begin{align}
& = \sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j} [gcd(x,y) = 1]\\
& = \sum_{i=1}^n \sum_{j=1}^m \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor [gcd(i,j) = 1] \\
\end{align}
$$
接下来的魔法需要莫比乌斯反演


$$
f(x) = \sum_{i=1}^n \sum_{j=1}^m \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor [gcd(i,j) = x]\\
g(x) = \sum_{d|x} f(d)
$$
显然
$$
g(x) = \sum_{i=1}^n \sum_{j=1}^m \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor [x|gcd(i,j)]
$$
然后提一下$x​$
$$
g(x) = \sum_{i=1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{x} \rfloor} \lfloor \frac{n}{xi} \rfloor \lfloor \frac{m}{xj} \rfloor
$$

然后因为我们求的是$f(1)$,则
$$
\begin{align}
f(1)& = \sum_{1|d} \mu(\frac{d}{1}) g(d)\\
& = \sum_{d=1}^{n} \mu(d) g(d)\\
&= \sum_{d=1}^{n} \mu(d) \sum_{i=1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{x} \rfloor} \lfloor \frac{n}{xi} \rfloor \lfloor \frac{m}{xj} \rfloor
\end{align}
$$
后面的显然可以数论分块,先预处理出$\sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor​$即可

显然,$\sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor​$ 和 $\sum_{i=1}^n d(i)​$ 是一样的

然而$d(i)$是积性函数,一起放给线性筛处理即可

0x02 代码

#include <cstdio>

inline int Min(int a, int b){return a < b? a: b;}

const int N = 51000;

int _case;
int n, m, pcnt;
long long ans;
bool vis[N + 20];
int pri[N + 20], mu[N + 20], smu[N + 20], d[N + 20], sum_d[N + 20], Min_pri[N + 20];

void pre(){
    mu[1] = 1; d[1] = 1; vis[1] = true;
    for(int i = 2; i <= N; i++){
        if( vis[i] == false ){
            pri[ ++pcnt ] = i;
            d[i] = 2; Min_pri[i] = 1;
            mu[i] = -1;
        }
        for(int j = 1; j <= pcnt; j++){
            if( pri[j] * i > N )
                break;
            vis[ pri[j] * i ] = true;
            if( i % pri[j] == 0 ){
                mu[ pri[j] * i ] = 0;    
                d[ pri[j] * i ] = d[i] / (Min_pri[i] + 1) * (Min_pri[i] + 2);
                Min_pri[ pri[j] * i ] = Min_pri[i] + 1;
            }
            else {
                mu[ pri[j] * i ] = -mu[i];
                d[ pri[j] * i ] = d[i] << 1;
                Min_pri[ pri[j] * i ] = 1;
            }
        }
    }
    for(int i = 1; i <= N; i++)
        smu[i] = smu[i - 1] + mu[i];
    for(int i = 1; i <= N; i++)
        sum_d[i] = sum_d[i - 1] + d[i];
}

int main(){
    pre();
    scanf("%d", &_case);
    while( _case -- ){
        scanf("%d%d", &n, &m);
        ans = 0;
        if(n > m) {int tmp = m; m = n; n = tmp;}
        for(int left = 1, rig; left <= n; left = rig + 1){
            rig = Min(n / (n / left), m / (m / left));    
            ans += 1LL * (smu[rig] - smu[left - 1]) * sum_d[n / left] * sum_d[m / left];
        }
        printf("%lld\n", ans);
    }
}

Luogu P1471 方差

我都快忘记还有一种公式叫完全平方公式了…

$$ (a + b) ^ 2 = a ^ 2 + b ^ 2 + 2ab $$

对,就是它,这道题目的核心

0x01 分析题目

题目链接: [https://www.luogu.org/problemnew/show/P1471]

让我们看看什么是方差

对于一个长度为 $ n $ 的数列 $ A $ ,其方差为
$$ \frac{1}{n} \sum^{n}_{i=1}(A_i – k)^2 $$
其中,$ k $ 为 $ A $ 数列的平均数

emmm, 看起来好复杂啊,等一下,这里有个平方

$$
\begin{align}
\frac{1}{n} \sum^{n}_{i=1}(A_i – k)^2 &= \frac{1}{n} \sum^{n}_{i=1}{A_i ^ 2 + k ^ 2 + 2A_ik} \\
&= \frac{1}{n} [\sum^{n}_{i=1}{A_i ^ 2} + nk^2 + 2k(\sum^{n}_{i=1}A_i)]
\end{align}
$$

恩,舒服多了

看一下操作,区间加,区间平均数(区间求和),区间方差?

区间方差怎么求?

先回到刚才的式子

然后,$ nk^2 $可以直接线段树求和处理出来
$2k(\sum^{n}_{i=1}A_i)$ 同上

$ \sum^{n}_{i=1}{A_i ^ 2} $怎么办?

回到完全平方公式,我们求平方和的时候,给数字$A_i$加$x$相当于把这个原$A_i^2$加上 $ (A_i + x) ^ 2 – A_i ^ 2 = (A_i ^ 2 + x ^ 2 + 2A_ix) – A_i ^ 2 = x ^ 2 + 2A_ix $

这不归根结底还是求和线段树吗……直接双标记线段树即可

0x02 代码

#include <cstdio>
const int N = 110000;
int op, n, m, x, y;
double k, z, tmp_double;
struct node{
    double sum, square;
    void operator+=(const node &b){
        this -> sum += b.sum;
        this -> square += b.square;
    }
}tmp;
node tree[N << 2];
double lazy[N << 2];
inline void pushup(int now){
    tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum;
    tree[now].square = tree[now << 1].square + tree[now << 1 | 1].square;
}
inline void pushdown(int now, int lson, int rson){
    if(lazy[now]){
        tree[now << 1].square  = tree[now << 1].square + (lazy[now] * tree[now << 1].sum * 2.0) + (lazy[now] * lazy[now]) * lson;
        tree[now << 1].sum += lazy[now] * lson;
        tree[now << 1 | 1].square  = tree[now << 1 | 1].square + (lazy[now] * tree[now << 1 | 1].sum * 2.0) + (lazy[now] * lazy[now]) * rson;
        tree[now << 1 | 1].sum += lazy[now] * rson;
        lazy[now << 1] += lazy[now];
        lazy[now << 1 | 1] += lazy[now];
        lazy[now] = 0;
    }
}
inline void query_add(int now, int left, int rig, int from, int to, double val){
    if(from <= left && rig <= to){
        tree[now].square = tree[now].square + ((val * tree[now].sum ) * 2) + (val * val) * (rig - left + 1);
        tree[now].sum = tree[now].sum + val * (rig - left + 1);
        lazy[now] += val;
        return ;
    }
    int mid = (left + rig) >> 1;
    pushdown(now, mid - left + 1, rig - mid);
    if(from <= mid) query_add(now << 1, left, mid, from, to, val);
    if(to > mid) query_add(now << 1 | 1, mid + 1, rig, from, to, val);
    pushup(now);
}
inline node query_sum(int now, int left, int rig, int from, int to){
    if(from <= left && rig <= to){
        return tree[now];
    }
    int mid = (left + rig) >> 1; node res = (node){0, 0};
    pushdown(now, mid - left + 1, rig - mid);
    if(from <= mid) res += query_sum(now << 1, left, mid, from, to);
    if(to > mid) res += query_sum(now << 1 | 1, mid + 1, rig, from, to);
    return res;
}
int main(){
#ifdef woshiluo
    freopen("luogu.1471.in", "r", stdin);
    freopen("luogu.1471.out", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%lf", &z);
        query_add(1, 1, n, i, i, z);
    }
    while(m--){
        scanf("%d", &op);
        if(op == 1){
            scanf("%d%d%lf", &x, &y, &z);
            k += (y - x + 1) * z;
            query_add(1, 1, n, x, y, z);
        }
        else if(op == 2){
            scanf("%d%d", &x, &y);
            tmp = query_sum(1, 1, n, x, y);
            printf("%.4lf\n", tmp.sum / (y - x + 1));
        }
        else if(op == 3){
            scanf("%d%d", &x, &y);
            tmp = query_sum(1, 1, n, x, y);
            printf("%.4lf\n", ( (tmp.square + (tmp.sum / (y - x + 1)) * tmp.sum - ( 2 * tmp.sum * (tmp.sum / (y - x + 1)) ) ) / (y - x + 1) ) );
        }
    }
}
]]>

论数学的重要性 — Studyingfather Dalao 的欢乐赛题解

比赛链接:[https://www.luogu.org/contestnew/show/8609]

0x-1


首先十分感谢 StudyingFater 大佬出的这场比赛让我们感受到这场数学的魅力(大雾 不过这个抄袭省选题目真的就有点….

0x00 奇怪的支付方式


题目链接:[https://www.luogu.org/problemnew/show/T36519]
题目一看,仿佛回到了小学题目的噩梦,然而作为一位正经Oier,尝试法可不是我们应该做的,仔细一看,发现这个操作似乎有点面熟,我们来把问题抽象一下
有一个整数\(n\)最少有几个数,确保中间任意两个数相加后得到值的集合为[1,n]
是不是有点眼熟?没错,这就在 初学DP(4) – 多重背包及其优化 – Codevs 3269 中的二进制优化法
     1
  10
100
看看上面这一串的数字是不是选择任意两个数加起来都可以得到(100)2以内的任何数? 由此可得,这道题目的答案就是n的二进制位数+1 当然快速求位数也很简单–\(log_2(n)\) 程序:
#include <cstdio>
#include <cmath>
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    printf("%d",(int)log2(n)+1);
}
惊不惊喜?意不意外?

0x01 我爱打飞盘


题目链接:[https://www.luogu.org/problemnew/show/T36562]
首先,作为一名乌市一中Oier,打飞盘是一项必备技能 读题!!!看到余数这个东西,第一个想到的就是同余定理 其次,对于数据范围搜索显然是会TLE的,我们就要另辟蹊径了 综合以上两个条件,很容易想到DP的思想,首先定义函数\(f(i,j)\) 其中\(i\)表示第\(i\)个数字,\(j\)表示以这个数字为结尾的数列余数为\(j\)有几种情况 很容易得到下面的代码:
#include <cstdio>
#include <cstring>
using namespace std;
int n,f,g,h,a[2100];
int dp[2100][2100];
int cnt;
inline int max(int a,int b) {return a>b?a:b;}
int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);dp[i][a[i]%f]++;}// 自己的情况先加上
    for(int i=1;i<=n;i++){
        g=a[i]%f;// 当前数对于f的余数
        for(int j=1;j<i;j++){// 遍历以前的情况
            for(int k=0;k<f;k++){// 遍历余数的情况
                h=(g+k)%f;  // 当前的余数
                dp[i][h]+=dp[j][k];// 累加
            }
        }
    }
    for(int i=1;i<=n;i++) cnt+=dp[i][0];// 统计余数为0的情况
    printf("%d",cnt);// 输出
}
但是时间复杂度呢?\(O(n^2f)\)显然这个数据范围承受起来有点费劲,我们要想办法优化 观察代码发现,我们每次都是就之前的状况累加,也就是说我们没有必要对之前的情况进行遍历,只需要记住累加和就行了,但是余数这个东西比较麻烦的在于,你如何确保不被累加运算? 滚动数组解决一切 不过是不是忘记了什么??? 取模啊!!! 所以正确的代码如下:
#include <cstdio>
#include <cstring>
using namespace std;
int n,f,g,h,l,a[2100],m=1e8;
int dp[2100],dp2[2100];
int cnt;
int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        g=a[i]%f;
        for(int k=0;k<f;k++){
            h=(g+k)%f;
            dp[h]+=dp2[k];
            dp[h]%=m;
        }
        for(int k=0;k<f;k++) {dp2[k]+=dp[k];dp2[k]%=m;dp[k]=0;}
        dp2[g]++;// 做到自己在把自己加上防止累加
    }
    printf("%d",dp2[0]);
}

0x02 硬币游戏


题目链接: [https://www.luogu.org/problemnew/show/T36547]
如果不是因为我有事情走的早的话我这题也能A 这题一眼看过去?博弈论?算了怎么高端的东西不好推,我们想想别的 显然,无论怎么操作,最后的结果一定是(int)n/m个m与n%m这样几堆硬币 所以我们计算总共可能的移动次数,对2取模即可得到结果 代码如下:
#include <cstdio>
#include <cmath>
using namespace std;
int T,n,m;
int temp,temp2;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        temp=n/m*(m-1);// 正确的操作应该是temp=n/m*m; temp-=m;合并了一下
        temp2=n%m;
        if(temp2>0) temp2--;// 有可能n%m==0
        if((temp2+temp)%2==0) printf("1\n");
        else printf("0\n");
    }
}

INFxINF END

]]>