문제
나연이는 A개의 사탕을, 다현이는 B개의 사탕을 갖고 있다. 두 사람은 아래와 같은 작업을 정확히 K번 반복하려고 한다.
- 둘 중 사탕의 개수가 더 적은 사람을 X, 더 많은 사람을 Y라고 하자. 단, 두 사람이 같은 개수의 사탕을 갖고 있다면 나연이가 X, 다현이가 Y이다.
- X가 P개의 사탕을, Y가 Q개의 사탕을 갖고 있을 때, Y는 X에게 자신의 사탕 P개를 준다. 결과적으로 X가 가진 사탕은 2P개, Y가 가진 사탕은 Q-P개가 된다.
작업이 끝나고 난 후, 두 사람이 각각 가지고 있는 사탕의 개수를 A',B'라고 하자. min(A',B')의 값은 얼마일까?
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 하나의 줄로 이루어지며, 각 줄에는 세 개의 정수 A,B,K (1≤A,B≤109, 1≤K≤2⋅109)가 공백 하나를 사이로 두고 주어진다.
[출력]
각 테스트 케이스마다, K번의 반복 작업이 끝나고 난 후, 두 사람이 각각 가지고 있는 사탕의 개수를 A',B'라고 할 때, min(A',B' )의 값을 한 줄에 하나씩 출력한다.
코드
#include <iostream>
using namespace std;
unsigned long long fpow(unsigned long long n,unsigned long long sum)
{
if (n == 0)
{
return 1;
}
unsigned long long result = fpow(n / 2,sum);
//result = result % sum;
result = (result*result)%sum;
if (n & 1)
{
result =(result*2)%sum;
}
return result;
}
unsigned long long find(unsigned long long a, unsigned long long b, unsigned long long k)
{
unsigned long long sum = a + b;
unsigned long long result = (fpow(k, sum) * a) % sum;
return min(result, sum - result);
}
int main()
{
int t;
unsigned long long a, b, k;
cin >> t;
for (int i = 0; i < t; i++)
{
cin >> a >> b >> k;
find(a, b,k);
cout << "#" << i + 1 << ' ' << find(a,b,k) << "\n";
}
return 0;
}설명
우선 이 문제는 시간초과의 문제만 없더라면 정말 쉽게 풀 수 있는 문제이다.
거듭제곱 계산에서 a의 1024제곱을 구할 때 a x a x a x a x a x a .......
의 방법으로 한다면 1024 즉 n번의 시간이 필요하지만
(a^512) * (a^512).... 처럼 a를 512번 곱하고 이 수를 서로 곱해주면 계산이 절반이 줄어드는 방식을 이용하면
X의 n제곱 수를 구하는데 필요한 시간복잡도를 O(log n)으로 줄일 수 있다.
이 문제에서 사탕의 개수 중 하나가 일반항으로 나타내면 k번 분배했을 때 (2^k*A)%C가 나온다. 그 이유는
정리
전체 사탕의 개수는 A+B=C, 일 때 C로 항상 일정하다.
n번째 단계에서 A개를 가지고 있는 사람이 B개를 갖고 있는 사람보다 더 적다면 2A가 되고
반대의 경우 C-A 개를 빼게 될 테니 2A-C 가 된다.
(2A-C) % C 를 하면 ((2A % C) - (C % C))%C 와 동일하고 C %C 는 0이니까 2A % C와 동일합니다.
이 때 모듈러 연산에 의하면 (2A-C % C) 와 (2A % C)는 동일하다.
이를 두 번 반복하면 ((2A % C)2) % C 가 될텐데 정리하면 ((2A %C) ( 2 % C ))%C를 거쳐서 (2^2 A) % C가 된다.
여기서 일반항을 구할 수 있다.
n번째 항에서 (2^n * A) % C 가 된다.
후기
절대로 혼자서 풀 수 없었다.. 교육을 들으면서 질문 글에 올라온 내용을 참조하여 풀었다. DP의 느낌처럼 몇번 반복하면서 규칙을 찾아 일반항을 구하는 느낌이 들었다.
