题目不用多说，算F(n):=sum_(m=2..n)phi(m)
算phi是个麻烦活：无论如何算phi(n)都需要对n做因式分解（或者用筛法优化）
所以，有没有办法不算这个东西？

有。

F(n)本质上是集合{1<=a<b<=n:gcd(a,b)=1}的大小。
可以想到，把整个集合{1<=a<b<=n}按照gcd(a,b)的值分类。
集合{1<=a<b<=n:gcd(a,b)=m}的大小当然是F(n/m)，于是得到递推关系

sum_{m=1..n-1} F(n/m)=n(n-1)/2，或者写成
F(n)=n(n-1)/2-sum_{m=2..n-1}F(n/m)

m大(m>sqrt(n))的时候，n/m的值当然会有重复；所以进一步写成
F(n)=n(n-1)/2-sum_{m=2..sqrt(n)}F(n/m)+F(m)(n/m-n/(m+1))

剩下的就是对于n较小时候的F(n)随算随存以免递归爆炸了

代码：
__int64 ph[70000]={0,0,1}; /* 预存的范围，70000是试验出来的； */
__int64 f(int n){
	int m;
	__int64 s=0,v=(__int64)n; /* 需要int64，否则n*n会溢出 */
	if((n<70000)&&ph[n]) return ph[n]; 
	for(m=2;m<n/m;m++){
		s+=f(n/m);s+=f(m)*(n/m-n/(m+1));
	}
	if(m==n/m)s+=f(m);
	s=(v*v-v)/2-s;
	if(n<70000) ph[n]=s;
	return s;
}

main(n){while(scanf("%d",&n),n)printf("%I64d\n",f(n));}

756K	94MS	C	275B