n제곱 계산
문제
이 문제에서 숫자 (3 + √5)^n 에 대한 소수점 앞에 마지막 세 자리를 찾아야합니다.
예를 들어, n = 5 일 때 (3 + √5)^5 = 3935.73982 … 이므로 답은 935입니다.
n = 2 인 경우 (3 + √5)^2 = 27.4164079 … 이므로, 답은 027입니다.
입력
첫 번째 입력 줄은 테스트 케이스의 수 T를 알려줍니다.
각각의 T 테스트 케이스는 행(라인)이 분할되어 주어지며, 각 테스트 케이스는 하나의 양의 정수 n을 알려줍니다.
출력
각 입력 테스트 케이스에 대해 다음과 같은 출력이 필요합니다.
1
Case #X: Y
여기서 X는 테스트 케이스 번호이고, Y는 숫자 (3 + (5)^(0.5))^n 의 마지막 세 정수입니다.
만일 소수점 앞의 숫자(정수)가 세 자리보다 작은 경우 출력에 정확히 세 자리가 포함되도록 앞에 0을 추가하십시오.
제한
1 ≤ T ≤ 100
2 ≤ n ≤ 2000000000
풀이
예전에 랜덤 마라톤에 이 문제의 small 버전인 Numbers(small)이 나왔었다.
그 때 푸는 아이디어를 보고, Big 버전도 언젠가 풀어야겠다 생각을 하고 있었는데
얼마전에 행렬 제곱, 분할 정복에 대해 공부하고서 이 문제를 풀 수 있겠다 싶어서 도전했다.
우선 문제는 3+√5^n 제곱에서 정수부를 구하는 문제이다.
고등학생이었다면 쉽게 생각할 수도 있었을 것 같은데 켤레수를 이용하면 쉽게 접근할 수 있다.
x = 3+√5, y = 3-√5로 놓고 문제는 x^n의 정수부를 구하는 문제라고 생각을 해보자.
이 때 3-√5는 0보다 크고 1보다 작은 수이므로 0 < 3-√5^n < 1도 성립한다.
x^n을 전개하고, y^n을 전개한 다음 더하면 √5가 있는 항들이 사라짐을 알 수 있다.
x^n을 전개한 항에서 √5가 남아있으려면 +부호를 가지고, y^n을 전개한 항에서 √5가 남아있으려면
-부호를 가져야하기 때문에 서로 상쇄되어 x^n + y^n의 결과는 정수 부분만 남게 된다.
그리고 0 < y^n < 1 이므로 x^n의 정수부는 x^n + y^n - 1과 같아진다.
참고 : https://seokjin2.tistory.com/13
이제 x^n + y^n을 어떻게 구할지가 문제가 된다.
3+√5와 3-√5를 두 근으로 갖는 방정식을 만들면 x^2 - 6x + 4가 된다.
이는 x^n - 6x^n-1 + 4x^n-2로도 볼 수 있고, x^n = 6x^n-1 - 4x^n-2이다.
3+√5와 3-√5가 두 근이므로 (3+√5)^n = 6*(3+√5)^n-1 - 4*(3+√5)^n-2이고
(3-√5)^n = 6*(3-√5)^n-1 - 4*(3-√5)^n-2 역시 성립한다.
tn = (3+√5)^n + (3-√5)^n으로 놓고 두 식을 더하면
1
tn = 6\*t(n-1) + 4\*t(n-2)라는 점화식을 구할 수 있다.
주어지는 n이 이십억이므로 분할 정복 거듭 제곱으로 풀어주기만 하면 된다.
위의 점화식을 행렬로 표현하면
로 표현할 수 있고, 좀 더 확장하면
이렇게 나타낼 수 있다.
양변에 n-1을 대입하면
이렇게 되니
1
2
|6 -4 |^n-1
|1 0 |
을 행렬 거듭 제곱 연산으로 풀어준 다음 나온 결과를 ans[2][2]라고 하면
t1 = 6, t2 = 28이므로 답은 ans[1][0]*28 + ans[1][1]*6 - 1 가 된다.
이 때 moduler 연산은 1000으로 하고, 음수 결과도 나올 수 있으니 음수일 때 1000을 더해줘야 한다.
구현 자체는 어렵지 않은데, 켤레 수를 이용해 점화식을 만드는 아이디어가 재밌었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
long long n, m, t;
bool flag=1;
long long mod = 1000;
vector<vector<long long>> v(2, vector<long long>(2));
vector<vector<long long>> ans(2, vector<long long>(2, 0));
cin >> t;
function <void(vector<vector<long long>>&, vector<vector<long long>>&)>
matrix =[&](vector<vector<long long>>& v1, vector<vector<long long>>& v2){
vector<vector<long long>> tmp(2, vector<long long>(2,0));
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
tmp[i][j] += v1[i][k]*v2[k][j];
tmp[i][j]%=1000;
}
}
}
v1 = tmp;
};
int ca=0;
while(t-->0){
ca++;
v[0][0]=6;
v[0][1]=-4;
v[1][0]=1;
v[1][1]=0;
ans[0][0]=1;
ans[0][1]=0;
ans[1][0]=0;
ans[1][1]=1;
cin >> n;
n--;
while(n>0){
if(n%2==1){
matrix(ans, v);
}
matrix(v,v);
n/=2;
}
m = ans[1][0]*28 + ans[1][1]*6 - 1;
m%=1000;
if(m==0)m=1000;
if(m<0)m+=1000;
if(m < 10) cout << "Case #" << ca << ": 00" << m << '\n';
else if(m < 100) cout << "Case #" << ca << ": 0" << m << '\n';
else cout << "Case #" << ca << ": " << m << '\n';
}
return 0;
}