UVA 10820 Send a Table——欧拉函数

UVA 10820 Send a Table——欧拉函数

欧拉函数模板题

不难发现除了（1,1）之外，其余二元组中两个元素均不相等。

设满足x

根据欧拉函数的定义，易知ans=phi（2）+phi（3）+、、、+phi（n）

#include #include #include #include using namespace std;const int maxn = 5e4+10;int phi[maxn];void init() { for (int i = 2; i < maxn; i++) phi[i] = 0; phi[1] = 1; for (int i = 2; i < maxn; i++) { if (phi[i]) continue; for (int j = i; j < maxn; j += i) { if (!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i-1); } }}int main() { init(); int n; while (~scanf("%d", &n) && n) { int ans = 0; for (int i = 2; i <= n; i++) ans += phi[i]; ans = ans * 2 + 1; printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。