백준 23888 (등차수열과 쿼리)

문제

23888번: 등차수열과 쿼리

초항 a와 공차 d가 주어지면 쿼리의 수에 따라 합이나 최대공약수를 출력하는 문제입니다.

쿼리가 1이고 구간 l과 r이 주어지면 [a(l) 부터 a(r)] 까지의 구간에 있는 수열의 합을 구하는 것입니다.

쿼리가 2이면 구간 l과 r이 주어지면 [a(l) 부터 a(r)] 까지의 구강에 있는 수열들의 최대공약수를 구하는것입니다.

 

먼저 쿼리 1의 해당 구간에 있는 수열들의 합을 구하기 위해서는 prefix sum 알고리즘을 사용하였습니다.

sumsum[1] = a;
    for (ull i = 2; i < 1010101; i++) {
        sumsum[i] = sumsum[i - 1] + a + (i - 1) * d;
    }

배열에 미리 누적합을 저장하는 방법입니다.

첫번째 항은 그대로 자기자신이므로 sumsum[1] = a 로 설정해줍니다.

그 다음 for문에서 sumsum[i]는 지금까지 누적합(sumsum[i - 1]) + 자기자신(a + (i - 1) * d) 을 해주면 됩니다.

 

쿼리 2는 최대공약수의 성질을 이용하였습니다.

gcd(a + cb , b) = gcd(a, b)

gcd(a, a + d) = gcd(a, d) 

gcd(a, b, c) = gcd(gcd(a, b), c)

if (l == r)cout << a + (l - 1) * d<<'\n';
else cout << gcd(a, d) << '\n';

주어진 수열은 공차가 d로 일정한 수열이므로 어느 구간에서나 모든 수열의 최대공약수는 gcd(a, d)를 만족합니다.

따라서 쿼리 2는 gcd(a, d) 이고 만약 l과 r이 같다면 그냥 그 구역에 있는 수를 출력하면 되므로 따로 코딩해줘야 합니다.

---

전체 코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ull a, d;
ull num, l, r;
ull sumsum[1010101];
ull q;
ll gcd(ull x, ull y);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> a >> d;
 
    sumsum[1] = a;
    for (ull i = 2; i < 1010101; i++) {
        sumsum[i] = sumsum[i - 1] + a + (i - 1) * d;
    }
    cin >> q;
    for (num, l, r; q > 0; q--) {
        cin >> num >> l >> r;
        if (num == 1)
            cout << sumsum[r] - sumsum[l - 1] << '\n';
        else
            if (l == r)cout << a + (l - 1) * d<<'\n';
            else cout << gcd(a, d) << '\n';
    }
    
 
    return 0;
}
ll gcd(ull x, ull y) {
    if (!y)return x;
    return gcd(y, x % y);
}