AtCoder Regular Contest #004 C : 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

問題概要

1~nの和の平均値からm in [1..n]を引いた数をX/Yとする。n,mの組として考えられるものをすべて列挙する。なければ指摘。

解法

式変形すると、n * ( (n+1)/2 - X/Y ) = m となる。1 <= m <= nなので、nは2*X/Yの近くだけを調べれば良い。こういうのは大抵うまくやればオーバーフロー回避できるようになってると思うのだけど、どうせ時間は足りてるのだから多倍長で十分。

acceptされたコード

D言語の多倍長にバグがあるらしく通らなかったのでpythonで書き直した。

import sys
s = raw_input().split('/')
x = int(s[0])
y = int(s[1])
tar = x / y * 2

found = False

for n in xrange(tar-100,tar+100):
	if(n > 0 and n * x % y == 0):
		m = n * (n + 1) / 2 - (n * x) / y
		if( 0 < m and m <= n ):
			found = True
			sys.stdout.write('%d %d\n' % (n, m))

if(not found):
	print  "Impossible"