連続する正整数の和について
"連続する正整数の和" に関する問題を2 題考えたのでそれについて.
(1)連続する2 つ以上の正整数で表すことが出来ない正整数はどのような数か?
まず, 連続する正整数の和として表すことが出来る数の性質について考えてみます.
i. 奇数個の連続する正整数である数を表すとき.
$m=2n+1$ とします. ($n$ は非負整数). このとき, $m$ 個の連続する正整数の和は, 中央の正整数を$x$ として, $(2n+1)x$ と表せます. すなわち, 奇数個の正整数で表せる整数は奇数の約数を持つということがここから分かります.
ii. 偶数個の連続する正整数である数を表す時.
$m=2n$ とします. ここで, 連続する正整数の最も左の数を$x$ とします. すると, $-x + 1$ から$x-1$ までの$2x - 1$ 個の整数を付け足した$2x + m - 1$ 個の整数を考えることで, i. と同じ議論ができます.
すなわち, 連続する正整数の和として表すことが出来る数は奇数の約数を持つことがわかります. また, 上の議論の途中で出てきた式から, 奇数の約数1 つに付き表現する方法が1 通り対応します.
ここで, どの正整数も1 という数を約数として持ちますが, これに対応する連続する正整数の和はその正整数自身です. このことから, "連続する2 つ以上の正整数で表すことができる数" = "1 以外の奇数の約数をもつ数" = "2 の冪でない数" ということがわかります.
(2)数$n$ を連続する正整数の和で表現する方法は何通りあるか?
これは(1) の議論から, $O(\sqrt{n})$ 時間で約数列挙をして, 奇数の約数の個数を数えてやればよいです. 復元も簡単にできて, (1) のi. とii. でやっている方法を用いればよいです.
#include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long lint; vector<lint> getDivisor(lint x) { vector<lint> vec; for (lint i = 1; i * i <= x; i++){ if (x % i == 0){ vec.push_back(i); if (i != x / i) vec.push_back(x / i); } } return (vec); } int main() { lint x; scanf("%lld", &x); vector<lint> v = getDivisor(x); vector<pair<lint, lint> > v2; for (int i = 0; i < v.size(); i++){ if (v[i] != 1 && v[i] % 2){ lint mid = x / v[i]; if (mid - (v[i] - 1) / 2 < 0){ v2.push_back(make_pair((v[i] - 1) / 2 - mid + 1, mid + (v[i] - 1) / 2)); } else { v2.push_back(make_pair(mid - (v[i] - 1) / 2, mid + (v[i] - 1) / 2)); if (v2[v2.size() - 1].first == 0) v2[v2.size() - 1].first++; } } } sort(v2.begin(), v2.end()); printf("%d\n", v2.size()); for (int i = 0; i < v2.size(); i++) printf("%lld %lld\n", v2[i].first, v2[i].second); return (0); }