[코딩 테스트 준비 - 기초] 2. 수학 (나머지 연산, 약수, 최대공약수와 최소공배수, 소수)

1. 나머지 연산

• (A + B) % M = ((A % M) + (B % M)) % M
• (A * B) % M = ((A % M) * (B % M)) % M
• (A - B) % M = ((A % M) - (B % M) + M) % M

 

📌 백준 참고 문제

• https://www.acmicpc.net/problem/10430
• https://www.acmicpc.net/problem/4375

 

2. 약수

1) N의 약수를 모두 구하는 방법

• 1부터 N까지 모든 자연수로 나누기 -> O(N)
• 1부터 √N까지 모든 자연수로 나누기 -> O(√N)
  • C가 A의 약수라면, A/C도 A의 약수임을 이용
  • 코드를 작성할 때, i<=sqrt(n) 과 i*i<=n 둘 다 가능하지만,
  • 컴퓨터는 실수를 근사값으로 나타내기 때문에 정수의 표현인 i*i<=n을 사용하는 것이 더 좋음!

#include <iostream>
using namespace std;

int main(){
	int n;
	cin>>n;

	//O(n)
	for(int i=1; i<=n; i++){
		if(n % i == 0)
			cout<<i<<'\n';
	}

	//O(√n)
	for(int i=1; i*i<=n; i++){ //i<=sqrt(n) == i*i<=n 
		if(n % i == 0){
			cout<<i<<'\n';
			if(i != n/i) cout<<n/i<<'\n';
		}
	}
    
	return 0;
}

 

 

2) f(N) = N의 약수의 합 일 때, g(N) = f(1) + f(2) + ... + f(N)을 구하는 방법

• f(N)은 N의 약수를 모두 구하는 방법과 동일
• "약수의 반대는 배수"라는 아이디어 활용
  • N이하의 자연수 중에서 i를 약수로 갖는 수의 개수는 [N/i]개
  • i를 약수로 갖는 수 = i의 배수
  • [N/i]은 N을 i로 나누었을 때의 몫
• 따라서 g(N) = [N/1]*1 + [N/2]*2 + ... + [N/(N-1)]*(N-1) + [N/N]*N -> O(N)

 

[백준 17425번 약수의 합]

• 테스트케이스를 반복하며 변하지 않는 값들은 매번 계산하지 않고 재사용하기
• f와 g의 자료형을 long long으로 설정하기
• 빠른 입출력 설정하기

#include <iostream>
using namespace std;

const int MAX = 1000001;
long long f[MAX];
long long g[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	for(int i=1; i<MAX; i++){ //i는 약수로 갖는 수
		for(int j=1; i*j<MAX; j++){ //i의 배수
			f[i*j] += i;
		}
	}

	g[1] = f[1];
	for(int i=2; i<1000001; i++){
		g[i] = g[i-1] + f[i];
	}

	int t, n;
	cin>>t;
	for(int i=0; i<t; i++){
		cin>>n;
		cout<<g[n]<<'\n';
	}

	return 0;
}

 

📌 백준 참고 문제

• https://www.acmicpc.net/problem/1037
• https://www.acmicpc.net/problem/17427
• https://www.acmicpc.net/problem/17425

 

3. 최대공약수와 최소공배수

• 유클리드 호제법 이용

int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a % b);
}

int lcm(int a, int b){
	int g = gcd(a, b);
	return a * (b / g); //g * (a / g) * (b / g)
}

 

📌 백준 참고 문제

• https://www.acmicpc.net/problem/2609

 

4. 소수

1) 어떤 수 N이 소수인지 아닌지 구하는 방법

• 2부터 N까지 나눠보기 -> O(N)
• 2부터 N/2까지 나눠보기 -> O(N/2) = O(N)
• 2부터 √N까지 나눠보기 -> O(√N)

bool isPrime(int n){
	if(n < 2) return false;
	for(int i=2; i*i<=n; i++){ //O(√N)
		if(n % i == 0) return false;
	}
	return true;
}

 

2) 어떤 수 N 이하의 모든 소수를 구하는 방법

• 에라토스테네스의 체 사용 -> O(NloglogN)
• 소수는 '2부터 n-1까지의 수로 나누어 떨어지면 안된다'를 활용한 것

#include <iostream>
using namespace std;

const int MAX = 1000001;
bool check[MAX]; //true -> i번째 값은 소수가 아님, false -> 소수임

int main(){
	int m,n;
	cin>>m>>n;

	check[0] = check[1] = true;
	for(int i=2; i*i<=MAX; i++){ //i*i가 MAX를 넘는 i의 배수는 이미 지워져 있다
		if(check[i] == false){
			for(int j=i+i; j<=MAX; j+=i) //i*i이전의 i배수는 이미 제거되어 있으므로 j=i*i로 써도된다. 
				check[j] = true; //i의 배수는 소수가 아님
		}
	}

	for(int i=m; i<=n; i++) { //m이상 n이하 소수 출력
		if(!check[i]) cout<<i<<'\n';
	}

	return 0;
}

 

📌 백준 참고 문제

• https://www.acmicpc.net/problem/1978
• https://www.acmicpc.net/problem/1929
• https://www.acmicpc.net/problem/6588