uva10820 - Send a Table(交表)

本文主要是介绍uva10820 - Send a Table(交表)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意很明了，，就不说题意了，，，

对于这个题来说，我们可以求出所有的互质二元组<i,j>(i!=j)的个数，然后乘以2，就是把互质二元组:<j,i>的个数也加上。对于<1,1>再特殊处理一下就好了，

一开始暴力做的。跑个1000两分钟还跑不出来呢，

其实刘汝佳书上说了个欧拉函数正合这个思路，phi[n]表示的正是(1,2,3,.....n)中与n互素的数的个数，

所以ans[n] = (phi[1]+phi[2]+phi[3].....phi[n])*2-1_____(减去1是因为<1,1>计数了两遍)

代码如下：

#include <cstdio>
#include <cmath>
#define M 50001
int phi[M] = {0};
void phi_table()
{phi[1] = 1;for(int i = 2; i < M; i++) if(phi[i]==0)for(int j = i; j < M; j+=i){if(phi[j]==0) phi[j] = j;phi[j] = phi[j]/i*(i-1);}
}
int main ()
{int n;phi_table();for(int i = 2; i < M; i++) phi[i] = phi[i]+phi[i-1];while(scanf("%d",&n),n)printf("%d\n",2*phi[n]-1);return 0;
}

这篇关于uva10820 - Send a Table(交表)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---