首页 > 代码库 > UVa 10820 (打表、欧拉函数) Send a Table
UVa 10820 (打表、欧拉函数) Send a Table
题意：
题目背景略去，将这道题很容易转化为，给出n求，n以内的有序数对(x, y)互素的对数。
分析：
问题还可以继续转化。
根据对称性，我们可以假设x<y，当x=y时，满足条件的只有(1, 1)。
设f(n)为 集合S{(x, y) | x<y且x、y互素} 的个数，则所求答案为2f(n)+1
f(n)表达式为：
，其中φ(n)为欧拉函数
这里有欧拉函数的一些介绍
1 #include <cstdio> 2 3 const int maxn = 50000; 4 5 int phi[maxn + 10], sum[maxn + 10]; 6 7 void phi_table(int n) 8 { 9 phi[1] = 0;10 for(int i = 2; i <= maxn; ++i) if(!phi[i]) //说明i为素数11 {12 for(int j = i; j <= maxn; j += i)13 {14 if(!phi[j]) phi[j] = j;15 phi[j] = phi[j] / i * (i - 1);16 }17 }18 }19 20 int main()21 {22 phi_table(maxn);23 sum[1] = phi[1];24 for(int i = 2; i <= maxn; ++i) sum[i] = sum[i - 1] + phi[i];25 26 int n;27 while(scanf("%d", &n) == 1 && n) printf("%d\n", 2*sum[n]+1);28 29 return 0;30 }
UVa 10820 (打表、欧拉函数) Send a Table
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。