电商平台正在建设中网站页面提示,网站维护的要求包括哪些,wp做网站需要多久,网站开发有哪些内容目录 1 基础知识2 模板3 工程化 1 基础知识
数a的欧拉函数 ϕ ( a ) \phi(a) ϕ(a)#xff1a;表示1~n中与n互质的数的个数。其中两个数互质#xff0c;是指这两个数的最大公约数为1。
根据定义#xff0c;我们可以写出如下方法#xff0c;
int gcd(int a, int b) {retu… 目录 1 基础知识2 模板3 工程化 1 基础知识
数a的欧拉函数 ϕ ( a ) \phi(a) ϕ(a)表示1~n中与n互质的数的个数。其中两个数互质是指这两个数的最大公约数为1。
根据定义我们可以写出如下方法
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}int phi(int a) {int res 0;for (int i 1; i a; i) {if (gcd(i, a) 1) {res 1;}}return res;
}但存在更快的求解方法见如下关键步骤
对数a进行分解质因子操作。 a p 1 α 1 ⋅ p 2 α 2 ⋯ p k α k ap_1^{\alpha_1} \cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k} ap1α1⋅p2α2⋯pkαk
unordered_mapint,int get_prime_divisors(int a) {unordered_mapint,int mp;for (int i 2; i a / i; i) {if (a % i 0) {int s 0;while (a % i 0) {a / i;s;}mp[i] s;}}if (a 1) mp[a] 1;return mp;
}计算数a的欧拉函数 ϕ ( a ) a ⋅ ( 1 − 1 p 1 ) ⋅ ( 1 − 1 p 2 ) ⋯ ( 1 − 1 p k ) \phi(a)a\cdot (1-\frac{1}{p_1}) \cdot (1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_k}) ϕ(a)a⋅(1−p11)⋅(1−p21)⋯(1−pk1)
int phi(int a, unordered_mapint,int mp) {int res a;for (auto [x, y] : mp) {res res / x * (x - 1);}return res;
} 可以将以上两步合并请看如下代码
int phi(int a) {int res a;for (int i 2; i a / i; i) {if (a % i 0) {res res / i * (i - 1);while (a % i 0) {a / i;}}}if (a 1) {res res / a * (a - 1);}return res;
}2 模板
int phi(int 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);return res;
}3 工程化
题目1输入n个数请分别求出它们的欧拉函数值。
#include iostreamusing 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;
}
