문제
https://www.acmicpc.net/problem/9613
걸린 시간
00 : 08 : 57
풀이
C++
#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int gcd(int a, int b){
if(b == 0) return a;
else return gcd(b, a%b);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin >> tc;
while(tc--){
int n;
cin >> n;
vector<int> num(n);
for(auto& i : num) cin >> i;
ll ans = 0;
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
ans += gcd(num[i], num[j]);
cout << ans << "\n";
}
return 0;
}
쌍의 개수가 100*99/2 = 495,000 개 까지 나올 수 있고 입력으로 주어지는 수가 최대 1,000,000 이므로 합이 int 형 범위를 벗어날 수 있다고 한다.
long long 형 데이터 타입에 모든 쌍의 gcd(최대공약수)를 누적시켜 출력하면 ac 를 받을 수 있다.
'Baekjoon' 카테고리의 다른 글
Baekjoon 7682번 틱택토 (0) | 2020.12.03 |
---|---|
Baekjoon 1956번 운동 (0) | 2020.12.02 |
Baekjoon 2931번 가스관 (0) | 2020.11.23 |
Baekjoon 16954번 움직이는 미로 탈출 (0) | 2020.11.22 |
Baekjoon 11066번 파일 합치기 (0) | 2020.11.22 |
댓글