math
-
[BOJ] 13172 ΣPS/BOJ 2022. 7. 18. 22:12
https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 알고리즘: 분할정복(제곱) $\frac{S_1}{N_1}+\frac{S_2}{N_2}에서,\\$ $\frac{S_1}{N_1}: a_1 \times b_1^{-1}\ \left(mod\ X\right)\\$ $\frac{S_2}{N_2}: a_2 \times b_2^{-1}\ \left(mod\ X\right)\\$ $\frac{S_1}{N_1}+\frac{S_2}{N_2} : a_1 \times b_1^{-1}\ \left(mod\ X\right)..
-
[BOJ] 2038 골롱 수열PS/BOJ 2020. 7. 17. 18:11
https://www.acmicpc.net/problem/2038 2038번: 골롱 수열 첫째 줄에 n(1≤n≤2,000,000,000)이 주어진다. www.acmicpc.net 알고리즘: Math (규칙-점화식 찾기) 접근: 1. 골롱 수열 이해하기 ... 2. N 그냥 규칙을 찾는 수학 문제이다... 독해력이 딸려서 그런지 골롱 수열을 이해하는데 한참 걸렸다. Golomb 수열: 모든 k에 대해 k가 수열상에서 f(k)번 등장하는 단조증가 수열. 수열을 이해했으면, 바로 규칙이 보일테고 그대로 코딩을 하면 되겠지만 N 범위가 상당히 크다. 따라서, k를 증가시켜가면서 f(k)를 대응시키다보면 O(N)으로 TLE를 받게 된다. 그래서 다른 방식으로 f(k) 값을 구해야한다. (k, f(k))로 수열을 ..
-
[BOJ] 1490 자리수로 나누기PS/BOJ 2020. 7. 15. 17:05
https://www.acmicpc.net/problem/1490 1490번: 자리수로 나누기 어떤 수 N이 주어졌을 때, N으로 시작하면서, N의 0이 아닌 모든 자리수로 나누어지는 떨어지는 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘: Math (최소공배수-소인수분해) 접근: 1. N의 0이 아닌 모든 자리수로 나누어 떨어져야 함. -> 각 자리수들의 최소공배수 $$Ans = lcm(a_0, a_1, ... , a_k)*t$$ 2. N으로 시작하면서 ... $$N*10^k \le Ans < N*10^{(k+1)}$$ $$let\ m=lcm(a_0, a_1, ... , a_k)$$ $$Then, {N*10^k\over m}\le t$$ $$\therefo..