๋ฌธ์
ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 9613๋ฒ GCD ํฉ ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค.
์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค.
์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์.
ํด๊ฒฐ๋ฒ
์ด๋ฒ ๋ฌธ์ ๋ ์ ํ์ ์ธ GCD ๋ฌธ์ ์๋ค.
์ ํด๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ชจ๋ฅด๋ ์ฌ๋์๊ฒ ์ด๋ ค์ด ๋ฌธ์ ์๊ฒ ์ง๋ง, ์ ํด๋ฆฌ๋ GCD ์๊ณ ๋ฆฌ์ฆ์ ์๊ณ ์๋ ์ฌ๋์๊ฒ๋ ์ ๋ ฅ ์ฒ๋ฆฌํ๋๊ฒ ๋ ์ด๋ ค์ ์ ๊ฒ ๊ฐ๋ค.
๋ง์ฝ ์ ํด๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ํด์ ์์ง ๋ชปํ๋ค๋ฉด ์ ํด๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ํตํ ์ต๋ ๊ณต์ฝ์์ ์ต์ ๊ณต๋ฐฐ์์์ ํ์ตํ๋ ๊ฒ์ ์ ๊ทน ์ถ์ฒํ๋ค.
์ ๊ทผ๋ฒ
๋ฐฐ์ด์ด ์ฃผ์ด์ง๋ค๋ฉด, 2์ค for ๋ฌธ์ ํตํด์ ๊ฐ๊ฐ ๊ตฌํ ์ ์๋ gcd๋ฅผ ๋ชจ๋ ๊ตฌํ๋ฉด ๋๋ค.
ํ์ง๋ง ์ฃผ์ํด์ผํ ๊ฒ์ด ํ๋ ์๋ค.
์๋ง ์ด ๋ฌธ์ ๊ฐ ์ ๋ต๋ฅ ์ด 30%์ธ ์ด์ ๋ ์ถ๋ ฅ ์๋ฃํ์ ํ์ธํ์ง ์์์ ์ผ๊ฒ ๊ฐ๋ค.
์ฃผ์ํ์
์ฐ์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๋จผ์ ๋ด๋ณด์.
- ํ ์คํธ ์ผ์ด์ค๊ฐ ์ต์ ์ ๊ฒฝ์ฐ 100๊ฐ
- tc ์์ GCD ์์ ๋ง๋ค ์ ์๋ ์์์ ๊ฐ์๊ฐ ์ต์ฝ์ ๊ฒฝ์ฐ 100๊ฐ
- ํ ์์๋ ์ต๋ 1,000,000 ๊น์ง.
์ฐ์ ์ ๋ ฅ n์ ๋ํ ์๊ฐ ๋ณต์ก๋๋ 10,000 ๋ฒ์ผ๋ก ์ถฉ๋ถํ ์ปค๋ฒ ๊ฐ๋ฅํ๋ค.
ํ์ง๋ง ์ด๋ค์ ํฉ์ ๊ตฌํ๋ ๋ฌธ์ ๋ก 100๊ฐ์ ์์๊ฐ ๋ชจ๋ 1,000,000 ์ธ์ ๋ฆฌ์ ์๋ผ๋ฉด?
100๊ฐ์ ์์๋ 2๊ฐ์ ์กฐํฉ์ ํ ์ ์์ผ๋ 100 C 2 ์ 100๋ง์ด๋ผ๋ฉด 49.5์ต์ด๋ผ๋ ์๊ฐ ๋์ค๋ฏ๋ก int ์ต๋ ๋ฒ์๋ฅผ ์ด๊ณผํ๋ค.
๊ทธ๋์ ๊ฒฐ๊ณผ๋ก ์ถ๋ ฅํ ๊ฐ์ ์๋ฃํ์ long์ผ๋ก ์ง์ ํด์ผํ๋ค.
์ ๋ต ์ฝ๋
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
while(t-- > 0) {
String[] inputs = br.readLine().split(" ");
int n = Integer.parseInt(inputs[0]);
int[] arr = new int[n];
long answer = 0;
for(int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(inputs[i + 1]);
}
for(int i = 0; i < arr.length-1; i++) {
for (int j = i + 1; j < arr.length; j++) {
answer += gcd(arr[i], arr[j]);
}
}
bw.write(answer + "\n");
}
bw.flush();
bw.close();
}
private static int gcd(int a, int b) {
while(b > 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}
๋ฌธ์ ํ๊ณ
์ด์ค for ๋ฌธ์ ๋ง๋๋๋ฐ ์ค๋ ์๊ฐ์ด ๊ฑธ๋ฆฐ ๋ฌธ์ ์ด๋ค.
์ ๋ ฅ n ํฌ๊ธฐ ๋ฐฐ์ด์ ๋ง๋ค๊ณ ํด๋น ๋ผ์ธ์ ๋ฐฐ์ด ๊ฐ์ผ๋ก ์ง์ ํ๋๋ฐ ๊ณ์ ๋์ณค๋ค.
๊ฑฐ๊ธฐ๋ค gcd ์๊ณ ๋ฆฌ์ฆ ์์ฒด์์๋b = a % b
๋ฅผ ํด์ผํ ๊ฒ์ ๊ณ์a = a % b
๋ผ ํด์ ์๊ฐ์ด ์ค๋ ๊ฑธ๋ ธ๋ค.
๋๊ธ