소인수 개수의 최대공약수 계산: 누적합과 펜윅 트리 적용
문제 분석 및 접근
주어진 데이터 크기를 고려하면 사전에 연산을 수행하는 전처리 과정이 필수적이며, 각 질의는 O(log N) 이하의 시간 복잡도로 처리해야 합니다. 함수 F(x)를 x의 서로 다른 소인수의 개수라고 할 때, 입력의 최댓값이 1,000,000이므로 1 ≤ F(x) ≤ 7의 범위를 가짐을 수학적으로 유도할 수 있습니다. 따라서 임의의 구간 [L, R]에 대해 F(x) 값이 1부터 ...
8월 24일 04:46에 게시됨
최대공약수와 최소공배수 곱의 수학적 동등성 및 알고리즘 최적화
문제 정의 및 수학적 배경
주어진 $n$개의 정수 배열에 대해, 전체 원소의 최대공약수(GCD)와 최소공배수(LCM)의 곱이 모든 원소의 곱과 일치하는지 판별해야 합니다. 이를 수식으로 표현하면 다음과 같습니다.
$$ \text{LCM}(a_1, a_2, \dots, a_n) \times \gcd(a_1, a_2, \dots, a_n) = a_1 \times a_2 \times \dots \times a_n $$
직접 계산 방식의 한계
가장 직관적인 ...
8월 14일 12:44에 게시됨
2023년 7월 상하이 컴퓨터학회 경쟁 플랫폼 초급반 문제 풀이
T1 행 우선 탐색
문제 개요
n×m 크기의 격자가 다음 규칙으로 채워져 있습니다:
열 1열 2...열 m
행 112...m
행 2m+1m+2...2m
행 32m+12m+2...3m
...............
행 n.........nm
정수 c가 주어지면, c가 위치한 행과 열을 "행 열" 순서로 출력합니다.
핵심 아이디어
격자의 구조를 분석하면 두 가지 핵심 관계를 도출할 수 있습니다:
열 계산: c를 m으로 나눈 나머지 ...
6월 28일 00:15에 게시됨
C++ 재귀 함수 기초: 문제 풀이 모음
재귀를 이용한 합계 계산
1부터 n까지의 정수 합계를 재귀 함수로 계산합니다.
#include <iostream>
using namespace std;
int sumRecur(int num) {
if (num == 1) return 1;
return num + sumRecur(num - 1);
}
int main() {
int n;
cin >> n;
cout > x >> n;
cout > n;
cout > n;
cout
6월 25일 23:38에 게시됨
약수 관련: 약수의 개수
N = (p1c1) * (p2c2) * ... * (pk^ck) 형태로 표현될 때
N2 = (p1(c12)) * (p2^ (c22)) * ... * (pk^ (ck*2)) 형태가 됩니다.
약수의 개수 f[N] = (c1+1)(c2+1)...(ck+1)
배수를 이용한 약수 개수 구하기
이 문제에서는 공식을 사용하지 않고, 약수를 구하는 대신 배수를 이용해 해결합니다.
#include <cstdio>
#include <cstring>
#include <iostream>
...
6월 2일 20:24에 게시됨
확장된 중국인의 나머지 정리 구현
기본 원리: 중국인의 나머지 정리 (CRT)
주어진 연립 동치식을 만족하는 해 x를 찾는 문제이다:
\[
\begin{cases}
x \equiv a_1 \pmod{r_1} \\
x \equiv a_2 \pmod{r_2} \\
\vdots \\
x \equiv a_n \pmod{r_n}
\end{cases}
\]
여기서 각 모듈러스 \( r_i \)들은 서로소일 경우, 이 시스템은 유일한 해를 가진다. 이를 통해 전체 해를 구성할 수 있다.
각 \( i \)에 ...
5월 27일 12:33에 게시됨