Full Solution

for point 3 in my previous post it should be (x-1)(y-1)-1-a.

Now i post the detail solution i promised. the solution in the previous post is what i read, but this one is what i came out, but essentially just linear congruences.

Solution: call a number good if it can be written in that form, bad otherwise.
write all positive integers in the following fashion:
1, 2, 3,..., x,
x+1,x+2,x+3,...,2x,
...
...
...
x(y-1)+1,x(y-1)+2,...,xy,
...

Now circle those number which are multiples of y: y,2y.3y...,xy.

to illustrate, let (x,y) = (7,11).

1, 2, 3, 4 ,5, 6, 7,
8, 9,10,__,12,13,14,
15,16,17,18,19,20,21,
__,23,24,25,26,27,28,
29,30,31,32,__,34,35,
36,37,38,39,40,41,42,
43,__,45,46,47,48,49,
50,51,52,53,54,__,56,
57,58,59,60,61,62,63,
64,65,__,67,68,69,70,
71,72,73,74,75,76,__,
...

now you could have notice: for last column all numbers are multiples of 7, and hence good. for other columns, 1.all number above circled ones are bad,
2.all number beneath are good.

if you can prove 1 and 2, then we have the answer to number of bad numbers:
floor(11/7) + floor (22/7) + floor(33/7)+...+floor(66/7)
or
floor(7/11) + floor (14/11) + floor(21/11) + ... + floor(70/11)

[we have an interesting identity here..., but it is quite easy to prove by normal means]

but notice the fraction parts of {11/7,22/7,...66/7} are just a permutation of {1/7,2/7,...,6/7}.

so we have (1/7)*[(11+22+...+66)-(1+2+...+6)] = 30.
now (x,y) = (7,11), so the formula can be rewritten as
(1/x)*[(y+2y+..+(x-1)y)-(1+2+..+(x-1))] = (1/2)(x-1)(y-1), the answer.

所有跟帖： 

• Thank you so much -cma- ♂ (0 bytes) () 11/05/2008 postreply 05:24:05

• 不客气 -Mushy- ♂ (0 bytes) () 11/07/2008 postreply 01:51:51