프로그래밍 공부 노트

https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 각 N_i와 S_i가 매우 크고, 또 MOD = 1000000007의 값이 매우 크므로 S_i / N_i를 페르마의 소정리, 즉 소수 p와 p의 배수가 아닌 자연수 a에 대해, a ^ (p - 1) ≡ 1 (mod p)를 이용해야 한다. N_i를 p - 1, 즉 MOD번 제곱한 값이 1이 되므로, N_i ^ (p - 2)는 N_i에 대한 곱셈의 역원이 된다. 따라서 모든 N_i와 S_i에 대해, S_i * (N_i ^ (MOD - 2))를 모두 더한..

https://www.acmicpc.net/problem/13171 13171번: A 음이 아닌 두 정수 A, X 가 있을 때 AX을 구하는 방법을 생각해보자. 물론 이 수는 매우 클 수 있기에, 1,000,000,007 (= 109 + 7)로 나눈 나머지를 구할 것이다. a mod x를 a를 x로 나눴을 때의 나머지라고 표 www.acmicpc.net X를 2진법으로 보았을 때, n의 자리의 값이 1인 각 n = 2^k에 대해 구하고자 하는 값은 A^(∑n)과 같다. #include typedef unsigned long long ull; #define MOD 1000000007 int main() { // ans = (A ^ X) % MOD ull A, X, ans = 1; // A를 입력받은 뒤 (..

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net n번째 피보나치 수 fib(n)에 대해, 행렬 {{1, 1}, {1, 0}}과 {{fib(n + 1), fib(n)}, {fib(n), fib(n - 1}}을 곱한 결과는 {{fib(n + 1) + fib(n), fib(n) + fib(n - 1)}, {fib(n) + fib(n - 1), fib(n)}}이다. 이 때 피보나치 수의 정의에 의해 fib(n + 1) + fib(n) = fib(n + 2)이고 fib(n) + fib(n - 1) = fib(n + 1)이므로, 위..

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net N과 K의 범위가 매우 크므로 페르마의 삼각형을 사용할 수는 없으므로, 이항계수 nCk = n! / (k! * (n - k)!)를 이용해야 한다. 단 n!, k!, (n - k)! 역시 매우 큰 값이므로, 각각을 MOD = 1,000,000,007로 나눈 값을 저장해야 한다. 각 팩토리얼을 한 값에 모듈러 연산을 취했기 때문에, n! / (k! * (n - k)!) 공식을 그대로 이용할 수는 없다. 따라서 페르마의 소정..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net B의 최댓값이 100,000,000,000이므로, A를 B번 곱할 경우 시간 초과가 발생한다. 따라서 B를 2진법으로 보았을 때, n의 자리의 값이 1인 각 n = 2^k에 대해 구하고자 하는 값은 A^(∑n)과 같다. #include #define MAX_N 5 #define MOD 1000 #define FOR for (int row = 0; row < N; row++) for (int col = 0; co..

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 수를 특정 수 MOD로 나눈 나머지에는 주기가 있는데, 이를 파사노 주기라고 한다. n이 10^18이므로 이 문제를 시간 안에 풀기 위해선 파사노 주기를 이용해야 하는데, MOD가 1,000,000인 경우 파사노 주기는 1,500,000임이 알려져 있으므로 n을 1,500,000으로 나눈 나머지를 이용한다. #include #define MAX_N 1500000 #define MOD 1000000 int main() { // fib[i % 3]: i번째 피보나치 수 i..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net A의 B승은 A를 B번 곱한 것으로도 볼 수 있지만, B % 2 == 1일 때 정답에 A를 곱하고, B를 2로 나누면서 A를 제곱하는 식으로도 계산할 수 있다. #include int main() { // ans = (A ^ B) % C unsigned long long A, B, C, ans = 1; scanf("%lld %lld %lld", &A, &B, &C); // B를 비트마스킹 형식으로 활용 while (B) { // B가 홀수라면 ans에 A를 곱한..