C 言語を使用して連続する自然数を求める
上位カテゴリ : 【C言語】 C言語インデックス
a. GitHub
Q. 少なくとも 2 つの連続する自然数を合計して、特定の数を作る方法の数を求めてください。例えば、
15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
方法は全部で4つあります。
補題
N を与えられた数とし、N = a × b、a = 2k の形となり、2 は b を割りません。すると、問題で要求されるウェイの数は、b の約数の数に等しくなります。
証拠。
k 個の自然数に n を加算することを考えます。
この場合、k は 2N の約数であることがわかります。
2N の任意の約数 k について、n を定義すると、次の条件が必要十分です。
2n + k - 1 と k はパリティが異なるため、一方が 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 を考慮すると、次のようになります。
#include <stdio.h>
#include <stdlib.h>
/* This source applies integer factorization to get the number of divisors 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