|
uchinyan |
|
掲示板、読みました。
解法としては．．．大きく分けて、 ・傾きに注目して数え上げる：#26814, #26818, #26819, #26820, #26825の後半(一部、考え方) ・何らかの点を基準にして数えていく：#26821, #26822, #26825の後半 ただし、これらは、基準の取り方によって、実際にはかなり異なります。 ・全体から重複を引く：#26816, #26817, #26825の前半 の三種類のようです。 なお、一般の状況として、#26815がありますが、こんな一般式になるとはね。 ふ〜む．．． (ちょっと追加) #26815のリンク先の一般式は、一般式を a(n) とすると、 a(n) = 1/2 * (f(n,1) - f(n.2)) f(n,k) = Sum{(n - |x|) * (n - |y|)}, - n < x < n, - n < y < n, (x,y) = k です。あまり説明がないのですが、(x,y) = k は、x, y の最大公約数が k、ということのようです。 さらに、0 はあらゆる整数を約数にもつ、と解釈して、(0,k) = (k,0) = k と考えるのでしょう。 この解釈のもとでは、 n = 4 f(4,1) = Sum{(4 - |x|) * (4 - |y|)}, - 4 < x < 4, - 4 < y < 4, (x,y) = 1 (x,y) = 1 となる x >= 0 を考えると、 x = 0, y = 1 x = 1, y = 0, 1, 2, 3 x = 2, y = 1, 3 x = 3, y = 1, 2 ここで、x -> -x, y -> -y なども可能なこと、0 -> -0 は意味がないこと、などに注意すると、 f(4,1) = 2 * {(4 - 0) * (4 - 1) + (4 - 1) * (4 - 0)} + 4 * {(4 - 1) * (4 - 1) + (4 - 1) * (4 - 2) + (4 - 1) * (4 - 3) + (4 - 2) * (4 - 1) + (4 - 2) * (4 - 3) + (4 - 3) * (4 - 1) + (4 - 3) * (4 - 2)} = 2 * {12 + 12} + 4 * {(9 + 6 + 3) + (6 + 2) + (3 + 2)} = 2 * 24 + 4 * 31 = 48 + 124 = 172 同様にして、 f(4,2) = Sum{(4 - |x|) * (4 - |y|)}, - 4 < x < 4, - 4 < y < 4, (x,y) = 2 x = 0, y = 2 x = 2, y = 0, 2 f(4,2) = 2 * {(4 - 0) * (4 - 2) + (4 - 2) * (4 - 0)} + 4 * {(4 - 2) * (4 - 2)} = 2 * {8 + 8} + 4 * 4 = 32 + 16 = 48 そこで、 a(4) = 1/2 * (172 - 48) = 62 となって、確かに、今回の答えと一致しますね。 x, y の最大公約数を考えていることから、これは、傾きを意識して数え上げているように思われますが．．． |
|
ネコの住む家
3月2日（木） 13:50:21
MAIL:uchi@sco.bekkoame.ne.jp 26826 |