//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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");
}
活动打卡代码
AcWing 2816. 判断子序列
数论——欧拉函数的自闭
啊上一期点赞是迅速的过了$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;
}
