응애개발자
article thumbnail
728x90

문제

https://www.acmicpc.net/problem/23888

 

접근 방법

  1. 첫째줄에 A : 첫항, D : 공차
  2. 둘째줄에 쿼리 갯수(테스트케이스 갯수)
  3. 셋째줄에 1 L R 또는 2 L R 값으로  첫번째 값이 1이면 L~R 까지 등차수열의 합을 ,2이면 L~R까지 의 최대공약수를 구하는 문제이다.
  4. 따라서 등차수열의 합은 공식을 이용해서 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());
    }
}

 

profile

응애개발자

@Eungae-D

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!