win10安装dx9:设M = 1010101…01 ,其中数字1出现k次,N = 1001001001001。试求出最小的k值使得M能被N整除

来源:百度文库 编辑:杭州交通信息网 时间:2024/05/05 05:16:43

设M = 1010101…01 ,其中数字1出现k次,N = 1001001001001。试求出最小的k值使得M能被N整除

解:注意到1010.....101×11=1111....111

而N×111=111.....11(共15个)

于是,取k=15,则有:

10101.....101(共15个1)=1111.....111(30个1)/11=N×111×(1000...(当中共14个0)..001/11)

而括号中显然是整数,即10101...101(共15个1)为N的倍数

下面证明15即最小值

假设m为k的最小值,即:101.....101(m个1)为N的倍数且m<15

则1010....101(15个1)-101....101(m个1)=101...101(15-m个1)×10^2m也是A的倍数

因为m是满足条件的最小值,所以m<15-m

m<8

N本身即为13位数,则m只能为7或8

经过计算则可知7和8均不满足条件

所以k=15即为满足条件的最小值

1