SRM385 Div2 1000
問題
要素数kの魔法の数列とは、正の整数x,dについて
x, x+d, x+2*d, x+3*d, ... , x+(k-1)*d
であるような等差数列である。
leftからrightまでの範囲の中で、k個の魔法の数列の合計として表現できる数字はいくつ存在するか。
[制約]
1<=left<=right<=10^9
k=2,3,4,5
考え方
1以上n以下でk個の等差数列の和で表現できる数の個数を返す関数calcを考える。
答えはcalc(right,k)-calc(left-1,k)で求まる。
calc(n,k)の中身について考える。
■もしk=2の場合、
x+(x+d)=2*x+1*dなので、これで表現できる数字は3,4,5,...であることがわかる。
なので、return max(0, n-2)となる。(-2は1,2の分)
■もしk=3の場合、
x+(x+d)+(x+2d)=3*x+3*d=3(x+d)なので、これで表現できる数字はx+dが2以上の整数すべてなので、6以上の3の倍数であるから、return max(0, n/3-1)となる。(-1は3の分)
■もしk=4の場合、
x+(x+d)+(x+2d)+(x+3d)=4*x+6*d=2(2x+3d)なので、これで表現できる数字は2x+3dが5,7,8,9,10,11,...(5と7以上の整数)であるので、10と14以上の偶数が表現できる。
なので、nが13以下の場合、10以上ならreturn 1、10未満ならreturn 0。
nが14以上の場合、return max(0,n/2-5)となる。(-5は2,4,6,8,13の分)
■もしk=5の場合、
5*x+10*d=5(x+2d)なので、これで表現できる数字はx+2dが3以上の整数すべてなので、15以上の5の倍数すべてとなる。
なので、return max(0,n/5-2)となる。(-2は5,10の分)
反省
[拡張ユークリッドの互除法あたりの話]
一般に、ax+byで表現される整数は、g=gcd(a,b)とおくと、
ax+by=g*( (a/g)x+(b/g)y )からgcd(a,b)の倍数となる。
なので、(a/g)x+(b/g)yで表現される数字について考察すればよい。
a/gとb/gは互いに素になるので、gcd(a/g,b/g)=1でx,yの組み合わせですべての数字を表現できる。
■match editorialsの説明
ここで、x,y>=1の整数だとすると、互いに素なa,bについてax+byが必ず表現できる数字を考える。ax+by=Nとすると、
N mod a = by mod a N mod b = ax mod b
である。Nがこの2つの式を満たすための最小のx,yは、
x=b y=a
でなければならない。よって、N=ab+ba=2abとなる。
したがって、Nが2ab以上の数字ならば上記の2つの式を満たすことができるので、この問題では、2ab未満の数字についてax+byで表現できるかをチェックすれば、任意のkについて解くことができる。
■注意
match editorialsでは、2ab以下の数字を見ればよいとあったが、実際はab以下の数字についてだけでよい。すなわち、abより大きい整数はax+byの形で書くことができる。
参考URL→http://oshiete.goo.ne.jp/qa/3426536.html
以下、URLの証明の書き写し。k=ax+by(x,yは自然数)を考える。
- 「b個の数k-a, k-2a,..., k-baの中にbで割り切れる数が存在する」ことを背理法で証明する。
k-aからk-baの中にbで割り切れる数が存在しないと仮定する。
k-aからk-baをbで割った余りはb-1通りしかないはずなので、余りがかぶる2つがあるはず。
それをk-uaとk-vaとする(0 < u < v <= bである整数)。
その2つの差、(k-va)-(k-ua)=(v-u)aはbで割り切れなければいけない。しかし、aとbは互いに素で、v-u <= b-u < bなので、bでは割り切れない。ゆえに矛盾するので、k-aからk-abの中にbで割り切れる数が存在する。
- 「abより大きいの整数はすべて表現できる」ことを証明
上の証明から、k-aからk-abの中でbで割り切れる数k-saがある。この数はk-sa=btとも表現できる。tはk-sa>k-ba>0なので、k=sa+btとなり、abより大きい整数はすべて表現することができる。
