플래티넘17 [백준 19577] 수학은 재밌어 [C] 풀이 euler_phi(x) = n/x가 성립하기 위해서는, n/x가 정수 이여야 한다. 즉, x는 n의 약수이어야 한다. n의 약수들을 모두 구한 후 오름차순으로 정렬해서 최소의 x를 찾아도 되고, 약수를 구해서 바로 계산을 해도된다. O(n^(1/2)) 만에 약수를 구하는 방법을 사용했다. 소스코드 #include #define min(a, b) a < b ? a : b int euler_phi(int n){ int euler = n; for (int p = 2; p*p 2021. 8. 30. [백준 5615] 아파트 임대 [C] 동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy + x + y이다. (x와 y는 양의 정수)동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다.동규부동산의 카탈로그에 적힌 아파트의 면적이 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 2^31-1이하인 양의 정수이다.출력첫째 줄에 있을 수 없는 아파트 면적의 수를 출력한다... 2021. 8. 29. [백준 11402] 이항 계수 4 [C] 풀이 Fermat’s little theorem을 기반으로 한 Lucas' theorem으로 풀이했다. Lucas' theorem는 다음과 같다. 쉽게, nCk를 M으로 나눈 나머지를 구하기 위해서는 N과 K를 M진 전개해 얻은 각 자릿수의 조합끼리 곱하고 M으로 나누면 된다. ex) input : 100 45 13 100 = 13*7 + 1*9 45 = 13*3 + 1*6 int result = 1; while (N || K){ result = result*nCk(N%M, K%M, M) %M; N /= M, K /= M; } nCk는 Fermat’s little theorem으로 구했다. 소스코드 #include int nCk(int N, int K, int M){ int A = 1, B = 1; fo.. 2021. 8. 28. [백준 16214] N과 M [C] 풀이 오일러의 정리를 이용해서 풀이하는 문제다. 이나... 자료가 너무 부족하다. 오일러의 정리에 대해 자료를 찾던 도중 다음과 같은 자료를 찾았다. a와 n이 서로소이면, a^m ≡ 1 mod n에서 m = EPF(n)을 만족하는 정수 m이 적어도 하나 존재한다. a (mod n)에 대한 차수가 위 식의 m이 될 수 있다. (N ^ f( N, EPF(M) ) ) % M을 재귀호출해 찍었다. 풀이했다. 입력받거나 전달받은 N과 M 둘 중 하나가 1일 때, 1을 반환해주면 위 식의 계산에 따라 원하는 결과를 얻을 수 있다. 단, 제곱을 구하는 과정에서 long long으로도 담을 수 없는 수가 나온다. (N^(N^N)) mod M != (N^((N^N) mod M)) mod M 이므로, M이 아닌 EPF(.. 2021. 8. 18. [백준 14860] GCD 곱 [C] 풀이 위의 예제는 다음과 같은 규칙이 있다. gcd(1, 소수) = 1 이므로 계산할 필요가 없으며, gcd(소수, 소수) = 소수 이다. gcd(N, M) = K일 때, gcd(N + K*i, M + K*i)는 모두 K이다. (단, i = 2~N or M) 위의 조건에서 얻은 K는 K의 제곱수가 존재할 경우 변경된다. N과 M크기를 이용해 K의 개수를 구할 수 있다. 두번째 조건에서 얻은 K들의 곱들과 세번째 조건에서 얻은 수의 중복을 피해야 한다. 다음과 같이 p+K*i (단, i = 0 ~ (p+K*i 2021. 8. 11. 이전 1 2 3 다음
