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"