头像

cht

《活着》




离线:1天前


新鲜事 原文

cht
1天前
缓更


新鲜事 原文

cht
10天前
acwing60000+了orz https://www.acwing.com/user/myspace/index/60041/


活动打卡代码 AcWing 2816. 判断子序列

cht
10天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++)scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++)scanf("%d", &b[i]);
    int i = 0, j = 0;
    while(i < n && j < m)
    {
        if(a[i] == b[j])i ++;
        j ++;
    }
    if (i == n) puts("Yes");
    else puts("No");
}


新鲜事 原文

cht
10天前
现在saber越来越冷了呢


新鲜事 原文

cht
12天前
要开新坑了,讲算法系列会慢点更新。 然后答应了大家会开算法竞赛进阶指南的坑qwq



cht
13天前

数论——欧拉函数的自闭

啊上一期点赞是迅速的过了$5$,咱们这期要求也不高:

点赞 + 收藏过$10$马上更新。

上次的同余方程

上次的贴过原题了,这次就不贴了。
好吧还是贴一下吧,方便后面证明。
简化题意:给定$a, b, m$,求一个$x$,使得$a\times x \equiv b(\mod m)$
随意输出任意一组解即可。
那这个怎么解呢?

遇到方程走三步

变形方程,部分求解,回归整体

第一步:变形方程

原式可以变为:
$a \times x = m \times y + b$
此时存在一个整数$y$,使得上边的代数式成立。
那么还可以再次变形成:
$a \ times x - m \times y = b$
看着是不是莫名熟悉?
再稍微改一下就行了。
令$y’$ = $-y$
然后就是exgcd了。
$a \times x - m \times y’ = b$
那他有解的条件就是$b$必须整除$gcd(a, m)$。
也就是说,如果上面的条件成立,那就一定有解。

第二步:部分求解

这一步我们需要把$x$和$y’$求出来,所以说是部分求解。
那这里就使用扩展欧几里得算法求解即可。

第三步:回归整体

然后用$y’$算回$y$。
这样就可以得出一个方程:
$a \times x = b + m \times y$
然后就ok了。
代码如下:

#include<iostream>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a, b, m;
        cin >> a >> b >> m;
        int x, y;
        int d = exgcd(a, m, x, y);
        if(b % d) puts("impossible");
        else cout << (long long) x * b / d % m << endl;
    }
    return 0;
}

进入正题:欧拉函数

啥是欧拉函数???

$N$欧拉函数是指$1-N$中与$N$互质的数的个数。

咋求呢?

先说公式,

前方含有大量$Latex$,可能导致加载过慢,非战斗人员请立即撤离,注意这不是演习!!!

$$
假设n的分解质因数为:\\
n = {p_1}^{\alpha_1} \times {p_2}^{\alpha_2} \times {p_3}^{\alpha_3} \times \ldots \times {p_k}^{\alpha_k}\\
则\varphi(n) = n \times (1 - \frac 1 {p_1}) \times (1 - \frac 1 {p_2}) \times (1 - \frac 1 {p_3}) \times \ldots \times (1 - \frac 1 {p_1}) \\
\\
懒得分开了,继续证明.jpeg\\
\\
先举个例子试一下。\\
6 = 2 \times 3\\
那么根据公式,\varphi(6) = 6 \times (1 - \frac 1 2) \times (1 - \frac 1 3) = 6 \times \frac 1 2 \times \frac 2 3 = 2\\
然后证明。\\
用到了容斥原理,这个东西以后再说8。\\
1. [1, n] -= (p_1 \times 1 + p_1 \times 2 +\ldots + p_1 \times \lfloor {\frac n {p_1}} \rfloor)\\ + (p_2 \times 1 + p_2 \times 2 +\ldots + p_2 \times \lfloor {\frac n {p_2}} \rfloor) \ldots (p_k \times 1 + p_k \times 2 +\ldots + p_k \times \lfloor {\frac n {p_k}} \rfloor)\\
上面那行Latex翻脸不认人。\\
更新集合后我们叫他S_1\\
2. S_1 += ((p_i \times p_j \times 1 + p_i \times p_j \times 2 +\ldots\\ + p_i \times p_j \times \lfloor {\frac n {p_i \times p_j}} \rfloor)) (注:i,j为[1, k]中的两个数)\\
更新上面的集合为S_2\\
3. S_2 -= ((p_i \times p_j \times p_l \times 1 + p_i \times p_j \times p_l \times 2 +\ldots\\ + p_i \times p_j \times p_l \times \lfloor {\frac n {p_i \times p_j \times p_l}} \rfloor)) (注:i,j,l为[1, k]中的三个数)\\
\ldots\\
用式子表示出来就是:n - \frac n {p_1} - \frac n {p_2} - \ldots - \frac n {p_k}\\
+ \frac n {p_1 \times p_2} + \frac {p_1 \times p_3} + \ldots + \frac n {p_{k - 1} \times p_k}\\
- \frac n {p_1 \times p_2 \times p_3} - \frac n {p_1 \times p_2 \times p_4} - \ldots - \frac n {p_{k - 2} \times p_{k - 1} \times p_k} \ldots\\
接着我们发现,按照\varphi(n) = n \times (1 - \frac 1 {p_1}) \times (1 - \frac 1 {p_2}) \times (1 - \frac 1 {p_3}) \times \ldots \times (1 - \frac 1 {p_1}) \\
这个式子展开后和刚刚得出的一样,ok搞定。\\
emm,我闻到了CPU的香味。\\
$$

继续,那我们改如何实现呢?
先贴上

给定n个正整数ai,请你求出每个数的欧拉函数。

欧拉函数的定义
$1 ~ N$ 中与 $N$ 互质的数的个数被称为欧拉函数,记$ϕ(N)$。
若在算数基本定理中,$N={p_1}^{a_1}{p_2}^{a_2}\ldots {p_m}^{a_m}$,则:
$ϕ(N) = N∗\frac {p_1 − 1} {p1} ∗ \frac {p_2−1}{p_2}∗\frac{p_m - 1}{p_m}$

输入格式

第一行包含整数$n$。

接下来$n$行,每行包含一个正整数$a_i$。

输出格式

输出共$n$行,每行输出一个正整数$a_i$的欧拉函数。

数据范围

$1 ≤ n ≤ 100,$
$1 ≤ a_i \times 10^9$

输入样例:

3
3
6
8

输出样例:

2
2
4

代码

这里直接贴代码了,就是套用了一下公式,数学章的代码实现起来都不是很难,主要在于公式的推导和证明。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        int res = x;
        for(int i = 2; i <= x / i; i ++)
        {
            if(x % i == 0)
            {
                res = res / i * (i - 1);
                while(x % i == 0) x /= i;
            }
        }
        if(x > 1) res = res / x * (x - 1);
        cout << res << endl;
    }
    return 0;
}

好了今天的分享就到这里了。

这是我的全部分享

bye~

下次聊筛法求欧拉函数,不见不散!!!(



新鲜事 原文

cht
14天前
跟新关注的小朋友讲一下,我们一般一周更新一期讲算法,然后卡常导论有时间会更新的,题解最近更新的比较少,然后就是做游戏系列的,会更新,大概再出一期讲算法我们就开坑!!!! 最后是这个提高课的同步啊,就是讲算法第二季,会再基础课的同步之后说啊。 有人问我为啥不开刷题的坑,这样吧,这个动态点赞过10咱们就开算法竞赛进阶指南的坑,好吧


新鲜事 原文

cht
15天前
https://www.acwing.com/activity/content/introduction/35/group_buy/2524/ 《算法竞赛进阶指南》第0x50章作者李煜东亲讲拼团优惠!


新鲜事 原文

cht
17天前
y总生日快乐!


新鲜事 原文

cht
17天前
分享稍微咕了一下