浙江省住房建设厅网站/交换链接或称互惠链接

如果你不知道什么是欧拉函数：请点这里！！！

下面让我们来检验一下对欧拉函数的理解。

873. 欧拉函数

给定$n$个正整数$a_i$，请你求出每个数的欧拉函数。
输入个数
第一行包含一个整数$n$.
接下来$n$行，每行包含一个正整数$a_i$。
输出个数
输出共$n$行，每行输出一个正整数$a_i$的欧拉函数。

思路：简单的模板题，不做解释。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
const int INF = 0x7fffffff;
const int MAXN = 1e6 + 10;int n;
ll a;ll oula(ll x){ll res = x;for(int i = 2; i * i <= x; i++){if(x % i == 0){res = res - res / i;while(x % i == 0) x /= i;}}if(x > 1) res = res - res / x;return res;
}int main(){cin >> n;for(int i = 1; i <= n; i++){cin >> a;cout << oula(a) << endl;}return 0;
}

874.筛法求欧拉函数

给定一个正整数$n$，求$1\dots n$中每个数的欧拉函数之和。
输入格式
共一行，包含一个整数$n$。
输出格式
共一行，包含一个整数，表示$1\dots n$中每个数的欧拉函数之和。

思路：简单的模板题，不做解释。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
const int INF = 0x7fffffff;
const int MAXN = 1e6 + 10;int n, oula[MAXN];
ll res;void Inou(){for(int i = 1; i <= MAXN; i++){oula[i] = i;}for(int i = 2; i <= MAXN; i++){if(oula[i] == i){for(int j = i; j <= MAXN; j += i){oula[j] = oula[j] - oula[j] / i;}}}
}int main(){cin >> n;Inou();res = 0;for(int i = 1; i <= n; i++){res += oula[i];}cout << res << endl;return 0;
}

仪仗队

作为体育委员，$C$君负责这次运动会仪仗队的训练。仪仗队是由学生组成的$N\times N$的方阵，为了保证队伍在行进中整齐划一，$C$君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QHUGlPGk-1686885701465)(F:\算法\图片\仪仗队.png)]

现在，$C$君希望你告诉他队伍整齐时能看到的学生人数。
输入格式
共一行，一个正整数$n$，$1\le n\le 40000$。
输出格式
共一行，一个正整数，表示$C$君可以看到的学生人数。

思路：我们把$C$君的位置看作$(0,0)$点，这样我们通过观察可以看到其余的点的$x,y$坐标的$gcd(x,y)=1$时，$C$君正好可以看见他。那么我们就可以通过欧拉函数，求出小于或等于它并与之互质的数的个数，因为图是关于$y=x$对称的，所以我们所求的欧拉函数要乘以$2$，并且要加上对称轴上看到的一位同学。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
const int INF = 0x7fffffff;
const int MAXN = 1e6 + 10;int n, oula[MAXN];
ll res;void Inou(){for(int i = 1; i <= MAXN; i++){oula[i] = i;}for(int i = 2; i <= MAXN; i++){if(oula[i] == i){for(int j = i; j <= MAXN; j += i){oula[j] = oula[j] - oula[j] / i;}}}
}int main(){Inou();ll res = 0;cin >> n;if(n == 1) cout << 0 << endl;//特殊判断当只有C君一位同学的情况else{for(int i = 2; i <= n; i++){res += oula[i-1] * 2;}cout << res + 1 << endl;}	return 0;
}