재귀 조심

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

거듭 제곱을 구해야하는 문제이고 입력의 범위가
long long 을 벗어나며 거듭 제곱을 for 문으로 구할 경우

시간 초과가 발생 (시간 제한이 0.5초 -> log n 을 고려) 한다.

따라서 단순히 for 문으로 곱하는 게 아닌
$N^A$ = $N^{A/2} * N^{A/2}$ 의 성질을 이용해
거듭 제곱을 재귀를 통해 구할 경우 시간 복잡도를 $log_2N$ 으로 줄일 수 있다.

그럼 이걸 구현하면 되는데

처음 구현한 방법이

long long go(long long A, long long B, long long C)
{
    if (B == 1)
        return A % C;

    long long ret = (go(A, B / 2, C) * go(A, B / 2, C)) % C;

    if (B % 2)
        ret = (ret * A) % C;
    return ret;
}

이처럼 재귀를 2번 구하는 걸로 했더니 시간 초과가 발생 했다.

0.5 초로 $log_2N$ 로 타이트하게 들어와야 하는 문제이므로 이를 2번 반복하여 시간초과가 발생한 것 같다.

long long go(long long A, long long B, long long C)
{
    if (B == 1)
        return A % C;

    long long ret = go(A, B / 2, C);
    ret = (ret * ret) % C;

    if (B % 2)
        ret = (ret * A) % C;
    return ret;
}

(사실 애초에 2번 구할 필요 없이 그냥 곱하는 걸로 생각했으면...)

---

항상 범위 신경

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

전에도 한번 풀었던 문제고 velog 에도 정리했던 문제인데...

곱셈 혹은 제곱과 같은 문제에서는 입력되는 n 의 범위가 커지면
long long 의 범위도 벗어나는 아주 큰 수가 될 수도 있다.

이럴 때는 나머지 연산을 통해 범위를 줄이는 게 좋다!!
(사실 문제에서 대부분 나머지 연산을 하라고 하기 때문에 연산 과정에서 나머지 연산을 추가하는 걸 생각해보자)

• 오버플로우로 시간 초과 발생

    while (cin >> n)
    {
        long long dec = 1;
        int cnt = 1;
        while (dec % n != 0)
        {
            dec = (dec * 10) + 1;
            cnt++;
        }
        cout << cnt << "\n";
    }

• 곱셈 과정에서 나머지 연산 추가

    while (cin >> n)
    {
        long long dec = 1;
        int cnt = 1;
        while (dec % n != 0)
        {
            dec = (dec * 10) % n + 1;
            cnt++;
        }
        cout << cnt << "\n";
    }

---

가우스 공식

https://school.programmers.co.kr/learn/courses/30/lessons/12912

두 정수 사이의 합을 구하는 문제로 for 문을 통해 구할수도 있지만

간단하게 가우스 공식 (등비수열의 합) 으로 구할 수 있다!!

간단히 가우스 공식에 대해 설명하면
1 ~ 100 까지의 숫자들의 합을 구할 때 이를 거꾸로 된 수열을 더하면

	1 	+  2  +  3  + ... + 99  + 100
+)	100 + 99  + 98  + ... +  2  +   1
	---------------------------------
    101 + 101 + 101 + ... + 101 + 101
    = 101 X 100 (1 ~ 100 사이의 숫자 개수) / 2

로 구할 수 있게 된다. 따라서 어떤 정수 a 와 b가 주어지고

a 와 b 사이의 정수 합을 구할 경우

$(a와 b의 합) * (a와 b 사이의 정수 개수) / 2 = (a + b) * (abs(a - b + 1) / 2$

로 구할 수 있는 것이다.

long long solution(int a, int b) {
    long long answer = 0;
    
    answer = (long long)(a + b) * (abs(a - b) + 1) / 2;
    
    return answer;
}

참고자료
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=emath202&logNo=220739347058
https://mathbang.net/609#gsc.tab=0

(계륵 일기 썸네일 완성!! 1시간 걸림...)