mojo's Blog

문제 링크 => https://www.acmicpc.net/problem/20412 20412번: 추첨상 사수 대작전! (Hard) 한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다. www.acmicpc.net 정수론 문제이다. 이 문제는 특별하게 m값이 소수로 주어지고 나머지 Seed, X1, X2 값은 0보다 크고 m 보다 작은 값으로 주어진다. 이때 a, c를 구하기 위해서 문제에서 주어진 식을 이용해서 a, c를 구해낼 수 있다. X1 = (a * Seed + c) (mod m) X2 = (a * X1 + c) (mod m) 위 식에서 아랫식을 윗 식을 빼주면 다음과 같은 결과를 얻는다. X2 - ..

문제 링크 => https://www.acmicpc.net/problem/14565 14565번: 역원(Inverse) 구하기 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 www.acmicpc.net N과 A이 주어질 때, 덧셈에 대한 역원과 곱셈에 대한 역원을 구하는 문제이다. 덧셈의 역원 => A + x = 0 (mod N) 이므로 x = N - A 이다. 이때, 1 Ax = 1 (mod N) 인데 x를 구하는건 쉽지 않다. 따라서 Extended Euclidean Algorithm 을 이용해..

ax + by = gcd(a,b) 에 대해서 gcd(a,b), x, y 를 구하는 방법 a = bq + r 이라고 할 때, q는 a를 b로 나눈 quotient, r는 a를 b로 나눈 remainder 이다. 위에 있는 식을 ax + by = gcd(a,b) 를 대입하면 bx' + ry' = gcd 와 같이 변형이 가능하다. 따라서 gcd(a, b) = gcd(b, r) 를 얻는다. (a, b) => (b, r) 과정을 반복하면 r = 0 인 경우가 오는데 이 때의 a가 최대공약수 g가 될 것이다. ax + by = gcd(a,b) 에서 gcd(a,b), x, y 를 구하는 코드 pair xGCD(ll a, ll b) { // returns {g, {x, y}}, ax+by=g if(b==0) retur..

이 문제는 각 학교마다 학생이 본선에 진출할 수 있도록 하는 사람의 최댓값을 출력하도록 하는 문제이다. 이때 학교의 수는 200,000 이고 학생의 수는 최대 MAX = 2,000,000 이 주어진다. 본선에 진출할 수 있는 학생의 수를 x 라고 한다면 x 의 배수가 되도록 하는 학교의 학생수를 전부 counting 하고 이 때 두 팀 이상이 본선에 참가할 수 있다는 것을 고려해줘야 한다. 그렇다면 처음에 각 학교마다 학생의 수 a 를 받을 때 a 명이 전체 학교에서 몇명인지에 대해서 알기 위해 stu_Count 배열을 사용하였다. 그리고 에라스토테네스의 체 방법을 이용하여 O(MAX * log(MAX)) 만큼 시간이 소요된다. 위에서 말한것처럼 본선 진출 가능한 학생의 수를 x 라고 할 때, 학생 수가..

문제 링크 => https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 2~5,000,000 범위의 숫자들이 1~1,000,000 개가 주어질때 각각의 숫자들을 소인수분해하여 소인수들을 오름차순으로 출력하는 문제이다. 우리가 일반적으로 알고있는 factorize 의 시간복잡도는 O(N^(1/2)) 이므로 대략 5,000,000의 루트에 1,000,000을 곱한다면 2,236,067,977.499789... 이므로 시간초과가 난다는 것은 확실하다. 따라서 이..

특정 범위 내에서 소수를 전부 구하고 싶을때 효율적인 방법은 에라토스테네스의 체이다. O(N) 만큼의 Memory를 사용하여 O(Nlog(logN)) 만에 특정 범위 내의 소수를 전부 구할 수 있다. 에라스토테네스의 체를 구하는 Code bool is_prime[1000005]; void sieve() { for(int i=2; i