레야몬

1. 문제 \(_{n}C_{k} \% 1,000,000,007\)을 구하시오 - 1 - \(N, K(1 \leq N \leq 4,000,000, 0 \leq k \leq N)\) \(_{n}C_{k} \% 1,000,000,007\) 2. 재정의 X 3. 해결 방법 \(P = N! \% M\)을 구하기 \(S = (N-K)! \times k! \% M\) 구하기 \(S^{1,000,000,005} \% M\) 구하기 \(P \times S \% M\) 구하기 4. 실수한 점, 개선할 점 nCr을 팩토리얼로 계산할 때 반복문 하나로 줄일 수 있다. #include using namespace std; typedef long long ll; // 소수 const int mod = 1000000007; // ..

1. 문제 수열 \(A_{i}\)가 주어진다. 연속된 부분 구간의 합이 M으로 나눠지는 구간의 개수를 구하여라 - 1 - \(N, M(1 \leq N 10^{6}, 2 \leq M \leq 10^{3})\) - 2 - \(A_{i}(0 \leq A_{i} \leq 10^{9})\) 연속된 부분 구간의 합이 M으로 나눠 떨어지는 구간의 개수를 출력한다. 2. 재정의 \(A_{i} + ... + A_{j} (i \leq j)\)의 합이 M으로 나누어 떨어지는 \((i, j)\)쌍의 개수 출력 3. 해결 방법 두 구간의 나머지가 M으로 같다면 두 구간의 합의 차의 나머지는 0이다. 즉 이를 이용해 누적합의 차가 k가 되는 구간(0, i)의 개수를 remain[k]에 저장하고 나서 kC2와 remain[0]을 ..

1. 문제 숫자 N개가 있다. 이를 M으로 나누었을 때 나머지가 모두 같게 되는 M을 찾고자 한다. \((M > 1)\) 가능한 M을 모두 찾으시오. - 1 - \(N(2 \leq N \leq 100)\) - N개의 줄 - \(1 \leq num \leq 1,000,000,000\) 같은 수가 2번 이상 주어지지 않음. 항상 M이 하나 이상 존재함 가능한 M을 공백으로 구분하여 모두 출력한다. M은 증가하는 순서대로 출력한다. 2. 재정의 \(num[1] \equiv ... \equiv num[N-1] (mod M)\)을 만족하는 1이 아닌 M 모두 구하기 3. 해결 방법 num[i] - num[1]의 GCD의 1이 아닌 모든 약수를 구한다. 유클리드 호제법을 이용하여 GCD를 구하고 sqrt(GCD)까..

아직 풀지는 못했고 언젠가는 정수론을 공부해야한다고 생각하기 때문에 정수론을 공부하고나서 풀어보려고 한다. 정수론 책 pdf https://blog.naver.com/PostView.nhn?blogId=mindo1103&logNo=221340552620&from=search&redirect=Log&widgetTypeCall=true&directAccess=false 정수론의 기초 https://divyanshkumarsblog.wordpress.com/2017/05/30/number-theory-i/ 그래서 결론은? https://divyanshkumarsblog.wordpress.com/2017/05/30/number-theory-ii-advanced-modular-arithmetic/ 중국인의 나머지..

1. 문제를 읽고 이해한다. 자연수 n \(1\leq n\leq 10^{12}\) GCD(n, k) = 1을 만족하는 자연수 $$ 1 \leq k \leq n $$ 의 개수 출력 2. 문제를 익숙한 용어로 재정의한다. n과 서로소인 수의 개수 출력(1도 포함) 3. 어떻게 해결할지 계획을 세운다. 에라토스테네스의 체로 소수를 구하기( $$ \sqrt{n} $$ 가지) O( $$ \sqrt{n} $$ ) 오일러 피 하수(Euler phi function)을 사용하기 4. 계획을 검증한다. O( $$ \sqrt{n} $$ ) = $$ \10^{6} $$ = 1, 000, 000 5. 프로그램으로 구현한다. 6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다. n과 서로소가 아니라 n의 소인수를 구..

#include #include #include #include #define FOR(i, k, N) for(int i=k; i> N; loc.push_back({0, 0}); FOR(i, 1, N) { int x, y; cin >> x >> y; loc.push_back({x, y}); } f(1, 0, 0, 0, 0); cout

#include #define LOOP(i, N) for(int i=1; i> N >> S >> E >> T; LOOP(i, N*5) { if(!((i-1)%5)) { LOOP(j, N) { int x; char tmp; cin >> tmp; x = tmp-'0'; if(x) pma[i][5*(j-1)+x]=ma[i][5*(j-1)+x]=1; //가중치가 0이 아니면 } } else pma[i][i-1]=ma[i][i-1]=1; } } void multiple(ll ma1[MAX_N*5+1][MAX_N*5+1], ll ma2[MAX_N*5+1][MAX_N*5+1]) //행렬 곱 { ll num[MAX_N*5+1][MAX_N*5+1]={}; //행렬 곱 후 값 LOOP(k, 5*N) { LOOP(i, 5*..

#include #include #include typedef long long int ll; char N[15]; //자연수 N ll num[10]; int main() { int n=-1; scanf("%s", N); for(int i=0; N[i]; i++) n++; //자릿수 세기 //앞에 있는 숫자 num[0]+=(n-1)*(ll)pow(10, n-1) - ((ll)pow(10, n-1)-1)/9 - n*(ll)pow(10, n-1); for(int i=0; i