题目

如果一个数只有1和0组成,这个数被37整除后余18,请问这个数至少要含有多少个1,

提问时间：2021-12-25

答案

1=1000(mod 37)
10=10(mod 37)
100=26=-11(mod 37)
解 x+10y-11z=18+37k
满足k>=0,x>=0,y>=0,z>=0的解,要求x+y+z最小
（x y z表示10^3n,10*10^3n,100*10^3n位上有x y z个1...）
解10y-11z=18+37k-x=u
y=-u,z=-u是特解
y=11t-u=11t+x-18-37k>=0
z=10t-u=10t+x-18-37k>=0
x+y+z=t+x+(20t+2x-36-74k) ,t的取值要让括号中值非负
取k=0,时t=2,x=0时上式最小=6（若t＝8）
取k>=1时,若1=5,从而x+y+z>=6(显然等号不成立)
若x=0,则t>5,从而x+y+z>=6(显然等号不成立)
所以x+y+z最小值是6＝0+4+2 即10^(3n+1)位上有4个1,10^(3n+2)位上有2个1,其余全0
验证26*2+10*4＝92＝18+37*2,正确.
例最小的数应该是：10 010 110 110