'Programming Problems/Number theory'에 해당되는 글 3건

Programming Problems/Number theory

주어진 소수들이 소인수인 수 중 N 번째 작은 수를 찾아보자.

ex)

소수 : [2,3]

N = 4

표현 가능한 수 : [1,2,3,4,6,8,9,12...]

답 : 4


풀이 : 수열이 각 소수의 곱셈에 따라 반복적으로 구성된다. 즉,


1 2 3 4 6 8 ..

이 포함되면

2 4 6 8 12 16 ..

3 6 9 12 18 24 ..

이 각각 포함된다.


따라서 1을 처음에 놓고, 다음 후보군은

2,3 중 하나다. 작은 2를 뺴고, 2의 다음 후보 4를 놓는다.

계속 가장 작은 것 하나를 빼고 진행한다.


이렇게 N 개 세면 된다.


타임 컴플렉시티는 


O(N * logK), K는 소수의 갯수이다. BST를 이용해서 최대값을 바로바로 조회하고 I/O를 해 주면 된다.

Programming Problems/Number theory

분수의 순환소수를 찾아보자.

분수가 주어지는 경우, 소숫점 표현법으로 바꿔보자. 순환소수가 있는 경우 괄호를 출력한다.

ex)

1/3 = 0.(3)

2/4 = 0.5(0)

22/7 = 3.(142857)


솔루션:


분모를 소인수분해해서 2와 5로만 구성되 있으면 그냥 나눈걸 출력한다. 끝에 (0)을 붙인다.

아니면 아래의 알고리즘을 쓴다.


정수로 나눈 값이 0이면 분자에 10을 곱한다. 정수로 나눈 값이 다음 자릿수다.

0이 아니면 그걸 그냥 그대로 붙이고 넘어간다.


지금까지 나온 소숫점 아래 숫자가 다시 나왔으면 순환은 거기까지다. 근데 이 경우에 순환소수가 바로 시작하지 않는 경우와 순환소수 내의 숫자가 반복되는 경우 패턴 매칭이 상당히 어렵다.


다른 시도로는 순환소수 분수 형태로 주어진 분수를 고치는 방법이다.. 근데 경우의 수가 상당히 많아서 쉽지 않을 듯?


9

90

99

900

990

999


...


32자리까지 근데 사실 32*31/2 개 밖에 없다. 따라서 이 중에서 성립하는 값이 있는지 확인하면 상당히 정확하다.


x/9999 = 3/7


x = 9999 * 3/7 이 정수가 나오는지?

아니면 (9999 * 분자) % 분모가 0인지 확인하자.


0이면 바로 순환소수로 바꿔준다.


9900 이었으면 


순환소수 2개 순환안하는거 2개


abc'd' 에서 abcd - ab = 분자 인 값을 찾는다. 뒤에서부터 빼면서 방정식을 풀어야 할듯


그러면 매우 정확하게 나온다.


--------------------------------


위의 곱해가며 구하는 패턴매칭을 조금 더 다듬어 보자.


아아 중요한 사실, 순환소수 반복은 해당 자릿수에서 "남은 값이 같은 경우부터 발생한다"


따라서 각 남은 값의 위치를 기록해 둔 후에, 남은 값이 같은 경우가 발생한 경우 그 처음 나온 남은 값의 위치부터 여기까지가 순환소수다..!!!!!


아 이거네.. ㅠㅠ


ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ


화이팅 니인생

Programming Problems/Number theory

N 보다 작으면서 3 또는 5의 배수인 숫자들의 합 구하기

처음에는 3또는 5만 소인수로 갖는 것들의 합 구하기로 생각해서, 3의 거듭제곱 중 가장 작으면서 큰거 i, 5의 거듭제곱 중 가장 작으면서 큰거 j 라고 하면

(i,j) 2중 for 루프의 모든 숫자들 중 N 보다 작은 것들을 전부 더해나갈 생각이었다. 갯수는 log^2N 이고 각각에 대해 합을 구하는건 단계별로 3씩 곱해나가는 셈이니까 1이 걸려서 총 시간 복잡도는 O(log^2N) 쯤 되겠다.


---


근데 이 문제는 "3 또는 5의 배수" 이기 때문에..


10 이면


3 6 9 = 18

5 = 5

tot : 23


매우 자명하게 

3 total = N/3 * (N/3*(N/3+1)/2)

5 total = same but 5

그리고 이 둘의 합을 하면 중간에 15의 배수가 겹치므로

15 total = same but 15


결과적으로 3과 5의 배수는

total = 3total + 5total - 15total 이다.


O(1) 알골이 되는 셈..