2416.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2416 on 2006-11-18 at 13:34:16 */
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 1024;
 
int main()
{
	int phi[N], sum[N], p[N], pn = 0;
	bool prime[N];
 
	memset(prime, true, sizeof(prime));
	for(int i = 2; i < N; i++) {
		if(!prime[i]) continue;
		p[pn++] = i;
		for(int j = i<<1; j < N; j += i) prime[j] = false;
	}
	phi[0] = phi[1] = 0;
	for(int i = 2; i < N; i++) {
		int n = i, m = i;
		for(int j = 0; m != 1; j++) {
			if(m%p[j] == 0) n = n*(p[j]-1)/p[j];
			while(m%p[j] == 0) m /= p[j];
		}
		phi[i] = n;
	}
	sum[0] = 0;
	for(int i = 0; i < N-1; i++) sum[i+1] = sum[i]+phi[i];
	
	int T;
	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		int n; scanf("%d", &n);
		printf("%d %d %d\n", t, n, 2*sum[n+1]+3);
	}
 
	return 0;
}