등차수열 구간의 최대공약수를 한번에 구하는 방법

1. 문제

 

23888번: 등차수열과 쿼리 (acmicpc.net)

23888번: 등차수열과 쿼리

 

2. 풀이

 

L번째 항부터 R번째 항까지의 합과 최대공약수를 구하는 문제

 

등차수열의 합은 초항이 $a_{1}$이고 항 수가 n개이며 공차가 d일때..

 

$$\frac{n(a_{1} + a_{n})}{2}$$

 

등차수열의 일반항은 a + (n-1)d이다.

 

그러면 L번째 항부터 R번째 항까지의 합은.. 초항이 a + (L-1)d이고 끝 항은 a + (R-1)d이며.. 항 수는 R-L+1개이니까..

 

a,d = map(int,stdin.readline().split())

q = int(stdin.readline())

for _ in range(q):
    
    c,l,r = map(int,stdin.readline().split())

    if c == 1:

        print((r-l+1)*(a+(l-1)*d + a+(r-1)*d)//2)

 

 

최대공약수는 $a_{l}, a_{l+1},...,a_{r}$에 대해서.. 반복적으로 구하면 될 것이다.

 

$gcd(a_{l}, a_{l+1}) = g_{1}$

 

$gcd(a_{1}, a_{l+2}) = g_{2}$

 

$gcd(a_{2}, a_{l+3}) = g_{3}$

 

...

 

근데 문제 제약조건이 L과 R이 1에서 1000000까지라 하나하나 구하면 틀림없이 시간초과일 것이다.

 

하지만 임의의 정수 k에 대해 $gcd(a,b) = gcd(a+kb, b)$라는 성질이 있다.

 

그러니까 $gcd(a,b) = gcd(a,a+d) = gcd(a, (a+d) - a) = gcd(a,d)$로 바꿀 수 있다는 뜻이다.

 

이를 확장하면..

 

$$gcd(a,a+d,a+2d,a+3d,...) = gcd(a,((a+d)-a), (a+2d-(a+d)), ...) = gcd(a,d,d,...) = gcd(a,d)$$

 

따라서 L번째 항부터 R번째 항까지의 최대공약수는 놀랍게도 gcd(a,d)로 O(1)만에 구할 수 있다.

 

물론 L = R이면 gcd(a,a) = a를 구해야한다.

 

from sys import stdin

def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

a,d = map(int,stdin.readline().split())

q = int(stdin.readline())

for _ in range(q):
    
    c,l,r = map(int,stdin.readline().split())

    if c == 1:

        print((r-l+1)*(a+(l-1)*d + a+(r-1)*d)//2)
    
    else:
        
        if l == r:
            
            print(a+(l-1)*d)
        
        else:
            
            g = gcd(a,d)

            print(g)