The Way

$a^n (mod m)$를 구하는 문제는 RSA 암호 등에서 사용되며 그 중요성이 크다. 단순히 곱해주는 방법이 가장 기본적이겠지만, 분할 정복을 사용하면 더 효율적으로 구하는 것이 가능하다. 보통 오래 걸리는 큰 숫자에서는 mod를 사용하지만, 나머지가 아닌 진짜 수를 원한다면 코드에서 mod 부분을 없애면 된다. 1. 기본적인 방법 숫자를 곱하며 mod 해주는 것을 n회 반복한다. 시간 복잡도는 $O(n)$이다. int pow1(int base, int index, int mod = 10) { long long r = 1; for (int i = 0; i < index; ++i) { r *= base; r %= mod; } return r; } 2. 분할 정복 $a^{2n} = (a^n)^2$이라는 ..

백준 온라인 저지(BOJ) 1009번 문제https://www.acmicpc.net/problem/1009 1. 문제 요약1번~10번의 이름을 가진 컴퓨터로 차례대로 분산 처리를 할 때, 마지막 데이터가 처리되는 컴퓨터의 번호는? 2. 알고리즘말은 복잡하지만, $a^b$의 일의 자리 수를 출력하는 문제이다.시간을 단축시키는 방법은 여기를 참고하자. 0일 경우 10으로 출력해야 한다. 3. 코드 #include int pow(int base, int index, int mod = 10) { int r = 1; while (index != 0) { if (index & 1 != 0) r = (r * base) % mod; base = (base * base) % mod; index >>= 1; } retur..

음원을 들으며, 과연 내가 들은 음원의 수익은 어떻게 분배되고 있을까 궁금한 사람들이 많을 것이다. 내가 현재 사용하는 스트리밍은 '멜론 프리클럽'인데,모바일 기준으로 DCF 파일 무제한 다운로드 가능, 음악 스트리밍 무제한 가능이며 한 달 11,400원이다.내가 지불하는 11,400원이라는 돈은 어떻게 분배되고 있는 것인지 궁금해 알아보는 시간을 가졌다. 스트리밍 기준으로 알아보고자 하니, 다운로드는 관심있는 사람이 알아보길 바란다. 1. 음원 전송 사용료2016년 2월자로, 문화체육관광부에서 지정한 곡당 사용료는월정액 스트리밍 기준 7원, 종량제 스트리밍 기준 14원이다. 이 중 권리자가 60%, 사업자가 40%를 가져간다고 하였다.사업자는 음원 서비스 업체로, 멜론, 네이버뮤직 등이 해당된다.즉, ..