블로그 옮겼습니다

문제 링크 N N; for(int i = 0; i > a; for(int j = 1; j * j = 2; i--){ if(!cnt[i]) continue; c[i] = (c[i] + cnt[i] * pow2[cnt[i] - 1]) % mod; for(int j = 2; j * j

\(N,M\le{10^5}\)인덱스 이외의 모든수는 \({10^6}\) 이하의 자연수 N개의 수로 이루어진 A[i] 가 주어지고, M개의 쿼리가 주어지는데 각 쿼리는 b, l, r 로 이루어지며구해야 할 것은 b의 약수들 중에 \(A_l, A_{l+1}, \dots, A_r\) 들을 모두 나눌 수 없는 약수들의 수 이다.이 각 쿼리들의 결과를 모두 합한 값을 출력하는 문제이다.어차피 각 수는 10^6 이하이기 때문에 이런 배열을 하나 만들 수 있다.last[i] : i로 나눌 수 있는 최대 인덱스그럼 오프라인으로 각 쿼리를 r 로 오름 차순 정렬한뒤 하나하나 봐주면서 현재 쿼리의 r까지 A[i]의 약수들에 대해 last[약수] 를 i로 업뎃해준다. 그런뒤 b의 약수들에 대해 last[약수] 가 l보다 크..

문제 링크 \( N\le{10^6}\)자연수 N이 주어진다. N을 네개의 소수의 합으로 분리할 수 있으면 그 네개의 수를 출력하고불가능하면 -1을 출력하는 문제이다. 우선 골드바흐의 추측이라는 것이 있다. 2보다 큰 짝수는 무조건 두개의 소수의 합으로 나타낼 수 있다는 것이다.내가 알기론 이미 꽤 큰 수(적어도 PS에서 주어지는 입력의 범위보단 큰 수) 까지는컴퓨터로 일일이 돌려보아 증명이 되었다고 알고있다. 그러니까 맞다고 생각하고 풀면된다 ㅎㅎ일단 입력으로 주어진 N이 홀수일 때와 짝수일 때로 나누어 보자.만약 홀수라면 골드바흐의 추측을 적용하기 위해 이를 짝수로 만들어 줘야 하므로 우선 하나의 수를 빼야하는데너무 많이 빼면 2이하가 될 수도 있으므로 가장 적게 빼는게 최선이므로 가장 작은 홀수 소수..

https://community.topcoder.com/stat?c=problem_statement&pm=11817 A, B, X

http://codeforces.com/contest/112/problem/D N x >> d; int cnt = 0; for(int j = 1; j * j

https://uva.onlinejudge.org/external/127/12775.pdf \(0 = 200\)일 때,Ax + By + Cz = P 위의 디오판토스 방정식의 음이 아닌 정수 해 (x, y, z) 의 개수를 구하는 문제이다.우선 위에서 주어진 두 조건 중 두번째 조건을 주목하자. C / gcd(A, B, C) 가 200이상이라는 말은 일단적어도 입력으로 들어오는 C가 200이상이라는 것을 알 수 있다. 그러면 z를 고정시키고 그에 대한 (x, y) 를 구하는식으로 계산한다치면, 최악의 경우에도 고정하는 z의 개수는 10^8 / 200 이하, 즉 50만개 이하가 된다. 그럼 z를 고정시키고 x, y 를 구해보자. 만약 ..

N 명의 사람이 각각 선물을 하나씩 준비해왔을 때 모두가 자신이 준비한 선물 이외의 선물을 갖도록 나눌 때그 경우의수를 구하는 문제 1 2 3 4 5 다섯명의 사람이 있다고 가정하자.맨 처음에 1번사람은 자신의 선물이 아닌 나머지 사람들의 선물, 즉 n-1 개의 선물을 가질 수 가 있다.그럼 그중에 하나의 경우인 1번사람이 2번사람의 선물을 가질 때를 생각해보자.그럼 2번사람이 받는 선물은 두가지 경우로 나뉜다. 첫번째, 1번사람의 선물을 갖는 경우. 그럼 1번 사람과 2번사람이 선물을 둘이 교환한 것과 같게 되므로D[i] : i명의 사람이 자신의 선물을 안갖도록 선물을 교환하는 경우의수일때, 교환한 두명을 제외한 나머지 n-2명에게 같은 행위를 반복하므로 D[n-2] 가 된다. 두번째, 1번 사람이 아..

1 T; for(int t = 1; t > P; ll S = 1e12; ll GCD = gcd(P*S, S); ll C = S/GCD; S = P * C; S -= C; ans[4] = S/4; if(S%4) ans[S%4]++; ans[0] = C - ans[1] - ans[2] - ans[3] - ans[4]; cout

예를 들어 소수 0.375 를 정수로 만들어 주기 위하여 곱해야 하는 최소 정수는 몇일까?답은 40이 나와야 한다.10의 거듭제곱꼴인 매우 큰 수 S가 있다고 하자. 그리고 주어진 소수를 p라고 해보자.그러면 p*S 는 정수가 될 것이 분명하다. (물론 가장 낮은 소수점 자릿수보다 10의 지수가 크거나 같아야만 한다)그렇다면 gcd(pS, S) 를 해보자. 만약 p가 정수였다면 gcd(pS, S)는 S임이 자명하다. 하지만 p 가 소수이기때문에p를 정수로 만들어 주기 위한 S의 최소 약수만큼이 빠질것이다. 그렇다면 p를 정수로 만들어 주기 위한 S의 최소 약수는 S/gcd(pS, S) 가 될 것이다. 그런데 잘 생각해 보면어떤 소수를 분수의 합꼴로 나타내보면, 즉 3*(1/10^(-1)) + 7*(1/1..

개인적으로 가장 알아야한다고 생각하는 네가지를 쓰겠다. 1번째\(\binom n k = \binom {n-1}{k} + \binom {n-1}{k-1}\) 예를 들어 생각해보면 쉬운데 어떤 반에서 n명의 학생중 k명의 대표를 뽑으려고하는데 이 때의 경우의 수는특정 학생 x 에 대해 두가지의 케이스로 나누어 생각해 볼 수가있다.학생 x를 뽑는 경우와 뽑지 않는 경우 이렇게 두 가지의 케이스이다.만약 학생 x를 뽑는다면 나머지 n-1 명의 학생들 중에 k-1명의 대표를 더 뽑아야 하므로 \(\binom {n-1}{k-1}\) 가지의경우의 수가 있으며, 학생 x를 뽑지 않는다면 나머지 n-1 명의 학생들 중에 k명의 대표를 뽑아야 하므로\(\binom {n-1}{k}\) 가지의 경우의 수가 있다. 그래서 두 ..