【코딩】 C 언어로 연속수

C 언어로 연속수

 

추천글 : 【C 언어】 C 언어 목차

---

Q. 몇 개(≥ 2)의 연속된 자연수를 더해서 주어진 수를 만드는 방법의 수를 구하라. 예를 들어,

 

15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

 

로서 총 4가지 방법이 존재한다.

 

Lemma.

주어진 수 N에 대해 N = a × b, a = 2^k꼴, 2 ∤ b라고 하자. 이때 문제에서 요구하는 방법의 수는 b의 약수의 개수와 같다.

 

Proof.

n부터 k개의 자연수를 더하는 것을 고려하자. 

 

n + (n + 1) + ··· + (n + k - 1) = (2n + k - 1) ÷ 2 × k = N

⇔ (2n + k - 1) × k = 2N

 

이때 k가 2N의 약수임을 알 수 있다.

임의의 2N의 약수 k에 대해, n이 정의되는 것과 다음 조건이 필요충분조건임을 확인하자.

 

2n + k - 1 ＞ k, 그리고 2n ≡ 0 (mod 2)

 

2n + k - 1과 k의 기우성이 다르므로 한 쪽이 2N의 홀수인 약수이면, 다른 한 쪽은 2N의 짝수인 약수이다. (두 번째 조건)

우선 조건 2n + k - 1 > k를 무시하고 생각해 보자.

2n + k - 1이 짝수이고 k가 홀수인 경우와 2n + k - 1이 홀수이고 k가 짝수인 경우로 나뉜다.

2N이 짝수라는 사실에 주의한다.

각 경우에서 경우의 수는 b의 약수의 개수와 같다는 것을 쉽게 확인할 수 있다.

그런데 2n + k - 1과 k가 기우성이 다르므로 두 개가 같은 경우는 존재하지 않는다.

또한 2n + k - 1과 k가 대칭적이므로 2n + k - 1 > k과 k > 2n + k - 1의 경우의 수는 같다.

따라서 2n + k - 1 > k를 고려하면 다음과 같다.

 

b의 약수의 개수 × 2 ÷ 2 = b의 약수의 개수

 

#include <stdio.h>
#include <stdlib.h>
/* This source apply integer factorization to get the number of divisor of a certain number */

int main(int argc, char *argv[]) {
	long long int n;
	scanf("%lld", &n);
	int Count_Divisor = 1;
	int i = 3;
	int count = 0;
    
	while(1){
		if(n % 2 == 1) break;
		n = n / 2;
	}
    
	while(1){
		if(n == 1){
			Count_Divisor = Count_Divisor * (count + 1);
			break;
		}
		if(n % i == 0){
                        count ++;
                        n = n / i;
                        i -= 2;
		}
		else{
			Count_Divisor = Count_Divisor * (count + 1);
			count = 0;
		}
		i += 2;
	}
	printf("%d", Count_Divisor);
	return 0;
}

 

입력: 2016.02.17 23:50