一、第五周学习总结表

本周学习完成情况

Contest	完成情况
数论1(快速幂、GCDLCM、扩欧)	6/16
数论2(同余与逆元、素数、抽屉原理)	8/14
组合数学1(杨辉三角、容斥原理、母函数)	5/8
组合数学2(卡特兰数、stirling数)	6/11
背包问题	11/18
Atcoder比赛+补题	6/10
郑州大学比赛+补题	6/12
小白月赛比赛+补题	3/5
总计	51/64

个人感悟
本周开始感觉有点力不从心，首先是每天的题目越来越多，但是学的也越来越难，主要是对数学知识理解的不够深刻，并且原本数学不怎么好。在学习数论的时候往往要很久才能理解，理解后也不能很快的应用在题目上面。另外每天题目很多，这周没来得及做的题目很多，却也没有什么时间去补题和写题解。有些灵感涌现时没有及时记录在题解内，很可惜。
希望下周可以及时的进行调整和自我反馈，越来越觉得有时候自我反馈和总结比一味的刷题更加重要。另外希望下周最后一周能对暑假所有所学的进行查漏补缺，把该补的题补完，该记录的模板概念都学完，并且做好对未来学习算法的规划。

二、本周学习新内容

1.求区间1-n之间与m互质的数的个数、

求不互质的个数

$互质=总数-不互质的个数$

ll primeNum(ll p, ll m) {
    v.clear();
    for (ll i = 2; i * i <= p; i++) {
        if (p % i == 0) {
            v.push_back(i);
            while (p % i == 0) p /= i;
        }
    }
    if (p > 1) v.push_back(p); //求n的素因子

    ll num = v.size(); //素因子的个数
    ll sum = 0;           // 1到m中与n不互素的数的个数

    //枚举子集，不能有空集，所以从1开始
    for (ll i = 1; i < 1 << num; i++) { //从1枚举到(2^素因子个数)
        ll cnt = 0;
        ll t = 1;
        for (ll j = 0; j < num; j++) { //枚举每个素因子
            if (i & (1 << j)) {        //有第i个因子
                cnt++;                 //计数
                t *= v[j];             //乘上这个质因子
            }
        }
        //容斥原理
        if (cnt & 1) //选取个数为奇数，加
            sum += m / t;
        else //选取个数为偶数，减
            sum -= m / t;
    }
    return m - sum; //返回1-m中与n互素的数的个数
}

2.求1-N含有0的个数

ll getCount0(ll num)
{
    if(num < 0) return 0;
    if(num == 0) return 1;
    ll base = 1;
    ll sum = 1;
    ll n = num;
 
    while (n != 0) {
        //区别在于这一行代码，减掉了1
        sum += base * (n / 10 - 1);
 
        int cur = n % 10;
        if (cur == 0) {
            sum += num % base + 1;
        } else if (cur > 0) {
            sum += base;
        }
 
        base *= 10;
        n = n / 10;
    }
 
    return sum;
}

3.博弈论

Nim博弈：

即n堆个物品，每次可以里面取任意个。

所有数异或如果为0则先手输

所有数异或如果不为0则先手胜

for (int k = 1; k <= n; k++)
{
    ans ^= num[k];
}

4.数论

1.唯一分解定理

任何一个大于1的自然数N，都可以被分解为有限个质数的乘积

即

$N=P_1^{a_1}*P_2^{a_2}*P_3^{a_3}*P_4^{a_4}*P_5^{a_5}······$

其中$P_i$均为质数且$P_1<P_2<P_3<P_4$

这样的分解称为$N的标准分解式$

2.欧几里得算法

欧几里得算法求gcd(a,b)

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

扩展欧几里得算法

ax + by = d = gcd(a, b)

$通解 = 特解 + 齐次解$

齐次解 :

ax + by = gcd(a,b);

通解：

设d = gcd(a, b)

所以 x = r b / d, y = －r a / d;

x = x0 ＋ b / d * k

y = y0 － a / d * k

在欧几里得算法中

b = 0 时：ax + by = gcd = a, 既：x = 1, y = 0;

b != 0 时：

ax + by = gcd = d (本层)
bx1 + (a mod b)y1 = d (裴蜀定理) （下一层）

bx1 + (a - [a / b] * b) * y1 = d
ay1 + b(x1 - [a / b] * y1) = d

所以：

x = y1
y = x1 - [a / b] * y1

3.同余定理

同余定理即：

$若(a-b)\bmod m = 0 ，则a\bmod m = b\bmod m$

证明：

$假设a\bmod m= b \bmod m\\ 可设a=m*k+d\\ 可设b=m*t+d\\ 则(a-b)\bmod m= (m*(k+t)+d-d)\bmod m=0$

其实就是余数在相减的过程中被减去了

其他性质
$(a+b) \bmod m=((a \bmod m)+(b \bmod m))\bmod m\\ (a*b) \bmod m=((a \bmod m)*(b \bmod m))\bmod m$
可以在题目中对大数取余的时候可以用到

$a\bmod m =b \bmod m\\ 则a^n \bmod m= b^n \bmod m\\ 则a+c \bmod m= b+c \bmod m\\ 则a*c \bmod m= b*c \bmod m\\ 则gcd(a,m)=gcd(b,m)\\\\ 若d|m\\则a\bmod d =b \bmod d\\\\ 若c\bmod m =d \bmod m \\ 则a*c\bmod m =b*d \bmod m\\ 则a+c\bmod m =b+d \bmod m\\$

两个数同余，那么他们的平方也同余，他们加上同样的数也同余

$a\bmod b=0\\ c\bmod d=0\\ a*b \bmod b*d =0$

4.逆元

逆元 —— 广义化的倒数 - 知乎 (zhihu.com)[https://zhuanlan.zhihu.com/p/449221995]

定义x为mod p下的逆元

$a*x\equiv1 \pmod p$,且a与p互质

应用:
求$\frac{a}{b} \pmod p$
先求出$b \bmod p$下的逆元，再乘上$ a \bmod p$
求解：

扩展欧几里得定理：

有解的条件是a与p互素

求解$a*x\equiv1 \pmod p$

转化为$ax+py=1$

即可以使用扩展欧几里得，解出x，再对x进行处理

#include <bits/stdc++.h>
#define ll long long
#define MOD 1e9 + 7
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int x1, y1;
    int d = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return d;
}
// a是求解数，b是模数
ll inv(int a, int b)
{
    int x, y;
    exgcd(a, b, x, y);
    x = (x % b + b) % b;
    return x;
}

费马小定理：

p比较小，且a，p互质，满足:

$a^{p-1} \equiv 1 (\bmod {p})$

$x \equiv a^{p-2} \pmod p$

即可以用快速幂求解

#include<bits/stdc++.h>
#define ll long long
#define MOD 1e9+7
using namespace std;
ll qpow(ll m,ll n,ll p){
    ll sum = 1;
    ll tmp = m;
    while(n != 0){
        if(n & 1 == 1) (sum *= tmp)%=p;
        (tmp *= tmp)%=p;
        n = n >> 1;
    }
    return sum;
}
ll inv(ll a){
    return qpow(a,MOD-2,MOD);
}
ll inv(ll a, ll mod){
    return qpow(a,mod-2,mod);
}

快速求阶乘逆元 $O(n)$：

因为有如下一个递推关系。

$inv[i+1]=\frac{1}{(i+1)}!$

$inv[i+1]∗(i+1)=\frac1i!=inv[i]$

所以我们可以求出$n!$的逆元，然后逆推，就可以求出$1…n!$所有的逆元了。

逆递推式为:

$inv[i]=inv[i+1]∗(i+1) \ (\bmod p)$

正递推式为：

$inv[i]=inv[i-1]∗(i)^{-1}\ \ \ \ (\bmod p)$

所以我们可以求出 $∀i,i!,\frac1i$的取值了

即：

$\displaystyle \frac{1}{i!} \times(i-1)!=\frac{1}{i} \pmod p$

线性推逆元：

求一连串数字mod一个p的逆元

初始化$1^{−1}≡1(\bmod p)$

设 $p=k∗i+r,(1<r<i<p)$

即$k=\frac pi,r=p\bmod i $

$k*i+r \equiv 0 \pmod p$

左右同乘$r^{-1},r^{-1}$

最终可以化简得到

$i^{-1}\equiv -\lfloor \frac{p}{i} \rfloor*(p \bmod i)^{-1} \pmod p$

inv[1] = 1;
for(int i = 1; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;

注意：
当$gcd(a,p)!=1$时，$a^{−1}≡0\bmod p$
不存在逆元，有时候需要特判

5.素数筛

埃式筛Eratosthenes

时间复杂度$O(n*log(logn))$
大O表示法中所展现的$logn$ 仅表示为对数级的数量级，一般认为以 2 为底，但并不做严格限制

/* 埃式筛原理:如果当前数组是质数，把他的所有倍数都筛掉 */
#include <iostream>
#define maxn 1000
bool isprime[maxn];
int prime[maxn];
//n生成从2-n
void eths(int n){
	int t=0;
	for (int i=2; i<n; i++) {
		isprime[i]=true;
	}
	for(int i=0;i<n;i++){
		if (isprime[i]) {
			prime[t++]=i;
			for(int j=2;i*j<n;j++){
				isprime[i*j]=false;
			}
		}
	}
}

欧拉筛

注意i=2
若是n以内包括n，则要i<=n
每个合数都用最小的质数去筛
核心：保证prime[j]*i，即被筛的那个数，里面的最小质因子是prime[j]，而不是i的因子。如果除通了，说明已经prime[j]已经是i的最小的质因子了。

#include <iostream>
#define maxn 10000000
using namespace std;
bool isprime[maxn];
int prime[maxn];

void Euler(int n){
	int t=0;
	for (int i=2; i<n; i++) {
		isprime[i]=true;//2-n初始化
	}
	for (int i=0; i<n; i++) {
		if (isprime[i]) {
			prime[t++]=i;
        }
        for (int j=0; j<t && i*prime[j]<=n; j++) {
          //判断条件j不能超过现有质数的个数，且相乘即被筛的数不能越上界
          isprime[prime[j]*i]=false;
          if (i%prime[j]==0) {//解析详见下文
            break;
          }
		}
	}
}

解析

prime[j]%i！=0，由于prime[j]从小到大遍历的质数数组中的一个。除不通，说明i的最小质因子比prime[j]还大，此时所有i的质因子都比primes[j]大，则相乘的那个数的最小质因子一定是prime[j]
prime[j]%i==0，则说明prime[j]已经便利到了i的最小质因数，如果此时不break;，则后面所筛掉的数，也就是prime[j]*i的最小质因子不是prime[j]，而是i的因子。不能保证prime[j]就是prime[j]*i的最小质因子，那么后面就会被重复筛掉，从而不能达到每个数只被筛一次的算法

6.GCD和LCM

性质：
- 可重复贡献:
  $gcd(a,b,c)=gcd(gcd(a,b),c)=gcd(a,gcd(b,c))$
- $gcd(a,0)=a,gcd(a,b)=gcd(a,-b)$
- $gcd(a,b)=gcd(b,a\bmod b)$
- $gcd(a,b)=d, gcd(a/d,b/d)=1$

多个值的GCD和LCM

7.矩阵快速幂

第i行第j列的数=第i行的第k个数*第j列的第k个数

代码

for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                t[i][j] = (t[i][j] + a[i][k] * b[k][j]);

8.卡特兰数

求解方法

通项公式法：

$Cat_n=\frac{C^{n}_{2n}}{n+1}=\frac{(2n!)}{(n+1)!n!}=C_{2n}^{n}-C_{2n}^{n-1}$

递推法:

$Cat_n=\Sigma Cat_k*Cat_{n-k},Cat_0=1$

ll c[N]={1};
void catalan(int n)
{
    for (int i = 1; i <= n; i++)
    {
        c[i] = 0;
        for (int j = 0; j < i; j++)
        {
            c[i] += c[j] * c[i - 1 - j];
        }
    }
}

$Cat_n=\frac{4n-2}{n+1}*C_{n-1},Cat_0=1$

优化
针对大数取模，可以使用通项公式
$Cat_n=\frac{C^{n}_{2n}}{n+1}$
配合预处理阶乘逆元求解
针对特大数，可用递推公式，配合高精度乘法/加法

三、题解一览

1.郑州大学 - K -魔法数

题目标签

数论

题目描述

定义满足以下条件的数为”魔法数”：

* 该数是正整数
* 该数的正约数有55个

16的正约数有1、2、4、8、16，因此16是魔法数。

20的正约数有1、2、4、5、10、20，因此20不是魔法数。

给定 l 和 r，求区间 [l,r]中魔法数的个数。

题目解析

结论题，知道结论就非常好做

一个大于1的正整数N，如果它的标准分解式为：

那么它的正因数个数为

所以求因子为五个的数

那么只有一种可能，他是某个质数的四倍，也就是$N=P_1^{4}$

所以先打素数筛，再把所取的数开四次方，求得范围

然后利用容斥原理，前缀和相减即可得到答案

通过代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define N 1001
bool isprime[N];
ll prime[N];
ll t=0;
void Euler(ll n){
	for (ll i=2; i<=n; i++) {
		isprime[i]=true;//2-n初始化
	}
	for (ll i=0; i<=n; i++) {
		if (isprime[i]) {
			prime[t++]=i;
        }
        for (ll j=0; j<t && i*prime[j]<=n; j++) {
          //判断条件j不能超过现有质数的个数，且相乘即被筛的数不能越上界
          isprime[prime[j]*i]=false;
          if (i%prime[j]==0) {//解析详见下文
            break;
          }
		}
	}
}
ll qpow(ll m,ll n){
    ll sum = 1;
    ll tmp = m;
    while(n != 0){
        if(n & 1 == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }
    return sum;
}
int main()
{
    Euler(N);
    ll sum[1000]={0};
    for (ll i = 0; i <t; i++)
    {
        sum[prime[i]]=1;
    }
    for (ll i = 1; i <= 1000; i++)
    {
        sum[i]=sum[i]+sum[i-1];
    }
    ll t;cin>>t;
    while (t--)
    {
        ull l,r;cin>>l>>r;
        int kfl=floor(sqrt(sqrt(l)));
        if(qpow(l,4)==l){
            kfl--;
        }
        int kfr=floor(sqrt(sqrt(r)));
        cout<<sum[kfr]-sum[kfl];
    }
    return 0;
}

2.组合数学1 - B - Visible Trees

题目标签

容斥原理

题目描述

给出一个m*n的方格，每个格子里都种了树

和树在一条直线上的视线都会被挡住，问在起点能看见多少树

题目解析

如图所示，只有视线的第一颗树会被看到，后面的树都被遮挡住了，可见被挡住的树都和第一颗树都在同一条直线上。

而后面被挡住的树的坐标$(x_i,y_i)$，自然也就是第一棵树的坐标$(x_1,y_1)$的倍数。

即$x_i=kx_1,y_i=ky_1$

所以$gcd(x_i,y_i)!=1$,也就是被挡住的数都是可以约分的

反过来说，没有被挡住的树，就是坐标$(x,y)$互质的。

而我们需要求$n*m$对的方格里的被挡住的树，也就是我们只需要.

对第$1-n$列,求出第$i$列，与坐标$i$互质的$y$的个数就可以了

通过代码

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
vector<ll> p;
//1到m之间与n互素的
ll cal(ll n, ll m) {
    p.clear();
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            p.push_back(i);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) p.push_back(n); //求n的素因子

    ll num = p.size(); //素因子的个数
    ll s = 0;           // 1到m中与n不互素的数的个数

    //枚举子集，不能有空集，所以从1开始
    for (ll i = 1; i < 1 << num; i++) { //从1枚举到(2^素因子个数)
        ll cnt = 0;
        ll t = 1;
        for (ll j = 0; j < num; j++) { //枚举每个素因子
            if (i & (1 << j)) {        //有第i个因子
                cnt++;                 //计数
                t *= p[j];             //乘上这个质因子
            }
        }
        //容斥原理
        if (cnt & 1) //选取个数为奇数，加
            s += m / t;
        else //选取个数为偶数，减
            s -= m / t;
    }
    return m - s; //返回1-m中与n互素的数的个数
}
int main(){
    ll T;cin>>T;
    while (T--)
    {
        ll m,n;
        cin>>m>>n;
        ll res=0;
        for (ll i = 1; i <= m; i++)//横坐标
        {
            res+=cal(i,n);
        }
        cout<<res<<endl;//
    }
    
}

3.组合数学1 - F - Ignatius and the Princess III

题目标签

组合数学；dp

题目描述

把一个数拆分成若干个数，问方案有几种

拆成的数可以一样，方案之间顺序不一样的只能算一种

比如5可以拆成

$(1,1,1,1,1) (1,1,1,2) (1,1,3) (1,4) (1,2,2) (2,3) (5)$

题目解析

如果用dfs，会超时

使用动态规划的思想，建立dp数组dp[i][j]

代表的是数字i被拆成最大数不超过j的方案数

比如dp[2][2]就有$(1,1) (2)$两种方案

于是我们可以推出动态转移方程

当我们遍历时，

j>i，则可以都可以赋值为dp[i][j-1]，因为当前数字也不过i这么大，就算能限制的数字j大于i，也没用，还是上一次的赋值
j=i，则可以赋值为dp[i][j-1]+1，因为j从$i-1→i$的过程中，新增加的一种方案，只有单独一个$(i)$
j<i，则可以赋值为dp[i][j-1]+dp[i-j][j]，当j<i时，能出现的方案两种
- 不选j——就是j-1时的所有方案
- 选j———-剩下的数i-j组成的所有方案
两种方案相加即可

于是可以得到动态转移方程

$\begin{align}&\\ \begin{cases}i>j,dp[i][j]=dp[i][j-1]+dp[i-j][j] \\ i=j,dp[i][j]=dp[i][j-1]+1\\i<j,dp[i][j]=dp[i][j-1]\end{cases} &\end{align}$

通过代码

#include<iostream>
#define N 1001
using namespace std;
int main()
{
    //将数字n,分解为不超过m的方案数
    // dp[1][1]=1;
    // dp[2][1]=1;dp[2][2]=2;
    // dp[3][1]=1;dp[3][2]=2;dp[3][3]=3;
    //当m=n，这时只能增加一种情况，也就是单个数，m的情况
    //当m>n，这时就是上一层的数，因为加不了别的了
    //当n<m，这时就是上一层不出现m的时候的方案数和出现m的方案数*n-m的方案数
    int dp[N][N] = {0};
    dp[1][1] = 1;
    for (int i = 1; i <= 121; i++)
        dp[i][1] = dp[1][i] = 1;
    for (int i = 1; i <= 121; i++)
    {
        for (int j = 1; j <= 121; j++)
        {
            if (j > i)
            {
                dp[i][j] = dp[i][j - 1];
            }
            else if (j == i)
            {
                dp[i][j] = dp[i][j - 1] + 1;
            }
            else if (i > j)
            {
                dp[i][j] = dp[i][j - 1] + dp[i - j][j];
            }
        }
    }
    int n;
    while (cin >> n)
    {
        cout << dp[n][n] << endl;
    }
    return 0;
}

4.排列组合 - G - 排列组合

题目标签

有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有”AB”,”BA”两种

题目描述

母函数

题目解析

使用指数型母函数，生成解

即把组合问题的加法与幂

级数的乘幂对应起来

不断将当前的一个括号内的多项式，与下一个括号内的多项式相乘

即可得到最终的每一个多项式的系数

但是要将系数now[n]*fac[n]

注意：

最后打印结果要保留整数，使用printf("%.0f\n",res);
每次乘完，要将nxt复制到now，并将nxt清零

通过代码

#include<bits/stdc++.h>
using namespace std;
int fac[20];
void init(int n)
{
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        fac[i] = fac[i - 1] * i;
    }
}
int main()
{
    init(20);
    int n, m;
    while (cin >> n >> m)
    {
        int num[20]={0};
        for (int i = 1; i <= n; i++)
        {
            cin >> num[i];
        }
        //每次乘后面一个
        double now[20] = {0};
        double nxt[20] = {0};
        now[0]=1;
        for (int i = 1; i <= n; i++) //从第二个开始
        {
            for (int j = 0; j <= num[i]; j++) //下一个
            {
                for (int k = 0; j + k <= m; k++)
                {
                    nxt[j + k] += now[k] / fac[j];
                }
            }
            memcpy(now, nxt, sizeof(nxt));
            memset(nxt,0,sizeof(nxt));
        }
        double res = now[m] * fac[m];
        printf("%.0f\n",res);
    }
    return 0;
}

5.郑州大学 - A - 想要更多的0

题目标签

二分；数学

题目描述

给你一个数n，求一个 [0,n]之间最大的整数m，使得输出区间 [m,n]之间的所有数时至少输出了k个0，如果无解请输出-1

1<= n,k <= 10^18^

题目解析

本题两个问题有待解决：、

数据范围过大

数据范围过大，思路是二分查找答案

查询一个点的0的个数，和n的0的个数进行比较，如果比较出来是不够k个

那么high=mid-1，如果够了或者超了那么low=mid

问题是边界的处理

如何获取前n个数含有的0的个数

使用

ll getCount0(ll num)
{
    if(num < 0) return 0;
    if(num == 0) return 1;
    ll base = 1;
    ll sum = 1;
    ll n = num;
 
    while (n != 0) {
        //区别在于这一行代码，减掉了1
        sum += base * (n / 10 - 1);
 
        int cur = n % 10;
        if (cur == 0) {
            sum += num % base + 1;
        } else if (cur > 0) {
            sum += base;
        }
 
        base *= 10;
        n = n / 10;
    }
 
    return sum;
}

通过代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
ll getCount0(ll num)
{
    if(num < 0) return 0;
    if(num == 0) return 1;
    ll base = 1;
    ll sum = 1;
    ll n = num;
    while (n != 0) {
        //区别在于这一行代码，减掉了1
        sum += base * (n / 10 - 1);
 
        int cur = n % 10;
        if (cur == 0) {
            sum += num % base + 1;
        } else if (cur > 0) {
            sum += base;
        }
 
        base *= 10;
        n = n / 10;
    }
    return sum;
}
int main()
{
    ull n,k;
    cin>>n>>k;
    ll low=0,high=n;
    __int128_t s=getCount0(n);
    while (low<high)
    {
        ull mid=(low+high+1)/2;
        if(s-getCount0(mid)>=k){
            low=mid;
        }else{
            high=mid-1;
        }
    }
    cout<<low+1;
    return 0;
}

22暑期ACM集训周记05

一、第五周学习总结表

本周学习完成情况

个人感悟

二、本周学习新内容

1.求区间1-n之间与m互质的数的个数、

2.求1-N含有0的个数

3.博弈论

4.数论

1.唯一分解定理

2.欧几里得算法

欧几里得算法求gcd(a,b)

扩展欧几里得算法

3.同余定理

同余定理即：

其他性质

4.逆元

应用:

求解：

注意：

5.素数筛

埃式筛Eratosthenes

欧拉筛

6.GCD和LCM

性质：

7.矩阵快速幂

8.卡特兰数

求解方法

优化

三、题解一览

1.郑州大学 - K -魔法数

题目标签

题目描述

题目解析

通过代码

2.组合数学1 - B - Visible Trees

题目标签

题目描述

题目解析

通过代码

3.组合数学1 - F - Ignatius and the Princess III

题目标签

题目描述

题目解析

通过代码

4.排列组合 - G - 排列组合

题目标签

题目描述

题目解析

通过代码

5.郑州大学 - A - 想要更多的0

题目标签

题目描述

题目解析

通过代码