728x90
문제
https://www.acmicpc.net/problem/23888
접근 방법
- 첫째줄에 A : 첫항, D : 공차
- 둘째줄에 쿼리 갯수(테스트케이스 갯수)
- 셋째줄에 1 L R 또는 2 L R 값으로 첫번째 값이 1이면 L~R 까지 등차수열의 합을 ,2이면 L~R까지 의 최대공약수를 구하는 문제이다.
- 따라서 등차수열의 합은 공식을 이용해서 N*{(2A+(N-1)D}/2, 최대공약수는 유클리드 호제법을 이용하여 구한다. 그리고 2번째에서는 L과 R이 필요가 없는게 A와 A+d, ... A+(N-1)d로 이루어져있기 때문에 첫항과 둘째항의 최대공약수나 둘째나 셋째의 최대공약수나, 셋째나 넷째의 최대공약수나 다 똑같다.(유클리드 호제)
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static StringBuilder sb;
private static BufferedReader br;
private static StringTokenizer st;
private static long A,D,Q;
private static long sumOrGCD, L, R;
//입력
public static void input() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
A = Long.parseLong(st.nextToken());
D = Long.parseLong(st.nextToken());
Q = Long.parseLong(br.readLine());
for(int tc = 0 ; tc<Q ; tc++){
st = new StringTokenizer(br.readLine());
sumOrGCD = Long.parseLong(st.nextToken());
L = Long.parseLong(st.nextToken());
R = Long.parseLong(st.nextToken());
process();
}
}
//등차수열의 합(공식)
public static long sumSequence(long n){
return n*(2*A+(n-1)*D)/2;
}
//유클리드호제법
public static long gcd(long a, long b){
while(a%b != 0){
long temp = a%b;
a = b;
b = temp;
}
return b;
}
//실행
public static void process() {
if(sumOrGCD == 1){
long sum = (sumSequence(R) - sumSequence(L-1));
sb.append(sum).append("\n");
}else{
if(L==R){
sb.append(A+(L-1)*D).append("\n");
}else{
if(D == 0) sb.append(A).append("\n");
else sb.append(gcd(A,D)).append("\n");
}
}
}
public static void main(String[] args) throws Exception {
input();
System.out.println(sb.toString());
}
}
'코딩테스트 > 백준' 카테고리의 다른 글
[Java] 백준 9417번 : 최대GCD (0) | 2024.05.21 |
---|---|
[Java] 백준 1990번 : 소수인팰린드롬 (0) | 2024.05.18 |
[Java] 백준 1407번 : 2로 몇 번 나누어질까 (0) | 2024.05.17 |
[Java] 백준 2436번 : 공약수 (0) | 2024.05.14 |
[Java] 백준 2725번 : 보이는 점의 개수 (0) | 2024.05.14 |