[중상] 서로소

서로소 : 유클리드 알고리즘(http://uwangg.tistory.com/24)

문제 : http://koitp.org/problem/RELATIVLEY_PRIME/read/

Github : https://github.com/ddulhddul/algorithm/blob/master/src/SW02_seoroso.java

1. 다틀림 ㅋㅋㅋㅋ 다시 풀어보자

소스코드

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

//class Solution {
class SW02_seoroso{
	
	public static void main(String[] args) 
			throws FileNotFoundException 
	{

		File file =new File("D:\\dev\\worksspace\\Solution\\src\\SW02_seoroso");
		Scanner sc = new Scanner(file);
//		Scanner sc = new Scanner(System.in);
		
//		long start = System.currentTimeMillis();
		
		while (sc.hasNext()) {
			int N = sc.nextInt();
			
			int[] nArr = new int[N];
			for (int i = 0; i < N; i++) {
				nArr[i] = sc.nextInt();
			}
			
			int[][] dp = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					dp[i][j] = maxNanu(nArr[i],nArr[j]);
				}
			}
			
			double answer = 0;
			for (int i = 0; i < N-1; i++) {
				for (int j = i+1; j < N; j++) {
					if(dp[i][j] == 1){
						answer += Math.pow(2, N-j-1);
					}
				}
			}
			
			System.out.println((int)(answer%10000003));
					
		}
		
//		long end = System.currentTimeMillis();
//		System.out.println("time "+ (end-start)/1000.0);
	}

	private static int maxNanu(int i, int j) {
		
		if(j == 0){
			return i;
		}else{
			return maxNanu(j,i%j);
		}
	}
	
}




/*
3
2 3 4

3
*/