수학 - 약수

약수

a = bc 를 만족하는 자연수c를 a의 약수라고 한다.
ex) 24의 약수 : 1, 2, 3, 4, 6, 8, 12, 24

for(int i=1; i<=n; i++)
{
if(n%i==0)
{
//i는 n의 약수
}
}

시간 복잡도 : O(n)

• c가 a의 약수라면, a/c도 a의 약수가 되어야한다.
  ex ) 1, 2, 3, 4, 6, 8, 12, 24
  3이 24의 약수라면, 24/3(=8)도 24의 약수가 되어야한다.

• c = a/c

• a = c의 제곱

• a=24일때

이것을 이용해서
절반(루트n)만 계산해도 전체를 알수있음
ex) 64의 약수 : 1, 2, 4, 8, 16, 32, 64
루트 64 = 8

문제1 ) 1037번 약수

링크 : https://www.acmicpc.net/problem/1037

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

내 풀이

'어떤 수 N의 진짜 약수가 모두 주어질 때' and 1과 자기 자신은 제외 이기 때문에
먼저 입력받은 수를 나열한다음에 첫 배열과 마지막 배열을 곱한다면 N을 구할수있음

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(reader.readLine());
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		int[] nums = new int[N];
		for(int i=0; i<N;i++)
			nums[i] = Integer.parseInt(tokenizer.nextToken());
		Arrays.sort(nums);
		System.out.println(nums[0]*nums[N-1]);
	}

}

인강 풀이

N의 진짜 약수 : M개
->최소 구하기 O(m)
->최대 구하기 O(m)
->2M->O(M)

문제2 ) 17427번 약수의 합2

링크 : https://www.acmicpc.net/problem/17425

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

과정

f(A) = A의 약수의 합
g(N) = f(1) + f(2) + ... + f(N)

입력 N = 5
출력 g(5) = 5보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값
g(5) = f(1) + f(2) + f(3) + f(4) + f(5)

시간복잡도 : f(N) = O(루트 N) or O(N)
g(N) = O(N의 제곱)
= O(N 루트N)
이 문제의 데이터는 1 <= N <= 1,000,000 이고,
제한시간은 0.5초이다.
시간복잡도가 O(N의 제곱)으로 푼다면
N의 제곱은 1조이기때문에 10,000초 걸린다.
그렇다면 O(N 루트N)은 100만 루트 100만(=1000) = 10억 = 10초이다.
그러므로 O(N 루트N)으로도 못푼다.

이 문제는 생각의 전환을 해야한다.
약수가 아닌 배수로 풀어야하는 문제

3의 배수는 3을 약수로 갖는 수
N이하의 자연수 중에서 1을 약수로 갖는 수(1의 배수)의 개수는 N/1개
N이하의 자연수 중에서 2를 약수로 갖는 수의 개수는 N/2개
.
.
N이하의 자연수 중에서 i를 약수로 갖는 수의 개수는 N/i개

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(reader.readLine());
		long g = 0;
		for(int i=1; i<=N;i++)
			g += (N/i)*i;

		System.out.println(g);
	}

}

시간복잡도 = O(N)

문제3 ) 17425번 약수의 합

링크 : https://www.acmicpc.net/problem/17425