#include <iostream>
using namespace std;

int mygcd(int x, int y)
{
	while(y>0){
		int temp = x%y;
		x = y;
		y = temp;
	}

	return x;
}

int main()
{
	// preprocessor
	
	int a[1001][1001] = {0};
	int s[1001] = {0};

	a[1][0] = 1;
	a[0][1] = 1;
	a[1][1] = 1;

	for(int y=1; y<1001; y++){
		for(int x=y+1; x<1001; x++){
			if(mygcd(x, y) == 1){
				a[x][y] = 1;
				a[y][x] = 1;
			}
		}
	}

	s[0] = 0;
	s[1] = 3;

	for(int i=2; i<1001; i++){
		s[i] += s[i-1];
		for(int j=1; j<=i; j++){
			s[i] += 2*a[i][j];
		}
	}

	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		int input;
		cin >> input;

		cout << i+1 << ' ' << input << ' ' << s[input] << endl;

	}

	return 0;
}

• Re:把int a[1001][1001] = {0};放到外面就可以了。用C++就可以过了。。 (0) B051401 2007-08-27 17:11:21
  • Re:把int a[1001][1001] = {0};放到外面就可以了。用C++就可以过了。。 (0) wenzhili 2010-11-02 17:27:49