3090.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3090  User Id:fzk 
Memory:8488K  Time:484MS
Language:Java  Result:Accepted

Source 

import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

public class Main {
	static int gcd( int a, int b ){
		int t;
		while( (a%=b) != 0 ) {
			t = a;
			a = b;
			b = t;
		}
		return b;
	}
	
	static int [][] s = new int[1001][1001];
	static int ans[] = new int[1001];
	
	static public void main( String [] str ) throws Exception{
		int n;
		int m;
		Scanner cin = new Scanner( System.in );
		n = cin.nextInt();
		for( int i=1; i<=1000; i++ )
		for( int j=1; j<=1000; j++ )
			if( gcd( i, j ) == 1 )
				s[i][j] = 1;
		
		for( int i=2; i<=1000; i++ ) {
			ans[i] = ans[i-1];
			for( int j=1; j<i; j++ )
				ans[i] += s[i][j] + s[j][i];
		}
		
		for( int k=1; k<=n; k++ ) {
			m = cin.nextInt();
			System.out.println( k+" "+m+" "+(ans[m]+3) );
		}
		
		
		return;
	}
}