装潢设计师工资一般多少_最新网游网络游戏新开服_东莞网站快速排名提升_怎么做公司网站推广

题目一：欧拉函数

873. 欧拉函数 - AcWing题库

分析（欧拉函数相关知识点）

互质数不了解可以参考之前笔记，以便更好了解：

数论—快速幂，欧几里得及其扩展，逆元，单位元_数论单位元函数-CSDN博客

👆👆👆

代码

核心公式，只需要对n实现质因子分解即可：

质数——acwing-CSDN博客

👆👆👆质数的笔记

#include<bits/stdc++.h>
using namespace std;int main() {int _;cin >> _;while(_ --) {int x; cin >> x;int ans = x; // 个数int i;for(i = 2; i <= x/i; i ++) {if(x%i == 0) {// 质因子判断// 先出后乘防止爆数据ans = ans/i*(i-1);// 先把i用了，然后约尽质因子i就可while(x%i==0) x/=i;}}if(x>1) ans = ans/x*(x-1);cout << ans << endl;}return 0;
}

题目二：筛法求欧拉函数 

874. 筛法求欧拉函数 - AcWing题库

分析

首先考虑暴力，但是每次都要求质因数分解。

算法优化：使用欧拉筛，来求欧拉函数，属于一种递推

代码

#include<bits/stdc++.h>
using namespace std;typedef long long ll;//欧拉筛
const int N = 1e6+10;
int prime[N], cnt;
bool vis[N];
//欧拉函数
int ol[N];int main() {int n;cin >> n;memset(vis,true,sizeof vis);ol[1] = 1;ll res = 0;for(int i = 2; i <= n; i ++) {if(vis[i]) {prime[cnt++] = i;ol[i] = i-1;}for(int j = 0; j < cnt && i*prime[j]<=n; j ++) {vis[i*prime[j]] = false;if(i%prime[j]==0) {ol[i*prime[j]] = ol[i]*prime[j];break;}ol[i*prime[j]] = ol[i]*(prime[j]-1);}}for(int i = 1; i <= n; i ++) {res += ol[i];}cout << res << endl;return 0;
}