|
uchinyan |
|
#30411，#30412，#30413，#30414，#30416
(ごめんなさい。計算がかなり冗長でした。修正しました。) 今更という感じですが，#30412の詳細です。 dobaさんのアイディアと基本的には同じだと思いますが，計算はもっと直接的です。 ・b が奇数の場合 ��{k=1,b-1} [k * a/b] = ��{k=1,(b-1)/2} {[k * a/b] + [(b-k) * a/b]} = ��{k=1,(b-1)/2} {[k * a/b] + [a - k * a/b]} ここで，a は整数，k * a/b は a, b が互いに素なので整数ではないです。そこで， [a - k * a/b] = a - [k * a/b] - 1 と書けます。最後の -1 がミソですね。これから， ��{k=1,b-1} [k * a/b] = ��{k=1,(b-1)/2} {[k * a/b] + a - [k * a/b] - 1} = (b-1)/2 * (a-1) = (a-1)(b-1)/2 になります。 ・b が偶数の場合 ��{k=1,b-1} [k * a/b] = ��{k=1,b/2-1} {[k * a/b] + [(b-k) * a/b]} + [b/2 * a/b] = ��{k=1,b/2-1} {[k * a/b] + [a - k * a/b]} + [a/2] ここで，同様に，[a - k * a/b] = a - [k * a/b] - 1 なので， = ��{k=1,b/2-1} {[k * a/b] + a - [k * a/b] - 1} + [a/2] = (b-2)/2 * (a-1) + [a/2] = (a-1)(b-2)/2 + [a/2] になります。 つまり， b が奇数のとき：(a-1)(b-1)/2 b が偶数のとき：(a-1)(b-2)/2 + [a/2] となって，後は，#30412のとおり b が偶数のときは [a/2] = (a-1)/2 なので，結局， ��{k=1,b-1} [k * a/b] = (a-1)(b-1)/2 になります。 この結果をながめていて，#30416の友人さんの解法も思いつきましたが，後の祭りですね (^^; |
|
ネコの住む家
7月27日（金） 13:57:03
MAIL:uchi@sco.bekkoame.ne.jp 30417 |