For positive triplet (n,x,y), n/(x*y)==n/x/y
even in integer division.
This should be useful to avoid overflow.
Let's prove this below.
if n.divmod(xy) is (a,b), n can be represented as:
n=axy+b (0<=b<xy)
On the other hand, if n.divmod(x) is (c,d) and c.divmod(y) is (e,f), n can be represented as:
n=cx+d (0<=d<x)
c=ey+f (0<=f<y)
n=x(ey+f)+d=exy+xf+d
Now suppose d is x-1 and f is y-1. Then xf+d
becomes x(y-1)+x-1=xy-1 (<xy)
.
This means 0<=xf+d<xy
and a(==n/(x*y))==e(==n/x/y)
has been proved.
Also, in n/(x*y)
, x and y are exchangable. So n/x/y == n/y/x
. (Q.E.D.)
検索用:自然数の3つ組(n,x,y)に対してn/(x*y)==n/x/y
は整数除算でも常に成立しますので、オーバーフローを避けるのに役立つでしょう。
170513
Actually this lemma is used for icbrt (integer cubic-root) used in http://qiita.com/cielavenir/items/2a685d3080862f2c2c47 .
180127
For fear, I confirmed small case...
#!/usr/bin/ruby
(1..10000).each{|n|
(1..100).each{|x|
(1..100).each{|y|
r0=n/(x*y)
r1=n/x/y
r2=n/y/x
if r0!=r1 || r1!=r2
raise [n,x,y].join(',')
end
}
}
}
https://qiita.com/cielavenir/items/d419b448d1c65eae2868 is another example where this lemma is useful.