【题目描述】 给出一个数A，你需要给出一个最小的数B，使得A与B的乘积只含有0和1。 【输入格式】 一个正整数A 【输出格式】 正整数B和A与B的乘积，两数之间用一个空格隔开 【样例输入】 6 【样例输出】 185 1110 【分析】 首先想到的是穷举2进制01串，但这样肯定会超时。 可以根据二进制01串（作为十进制数运算）除以A的余数进行递推，因为如果两个位数相同的01串除以A的余数相同，则在它们的最高位前再加个1后，两个新的01串除以A的余数仍然相同。而题目求的是最小的01串，故只需记录值较小的01串即可。 再利用mod运算的两个性质： (a*b) mod n=(a mod n)×(b mod n) 10^k mod n=(…(((10 mod n)×10) mod n)×10…) mod 10 高精度运算就可以避免了。
var i,n,k,len,r,tmpf,tmpl:longint; flag:boolean; long,father:array[0..10000]of longint; begin read(n); if n=1 then begin write(1,' ',1);halt; end; fillchar(father,sizeof(father),0); fillchar(long,sizeof(long),0); long[1]:=1; r:=1; len:=1; while long[0]=0 do begin r:=r*10 mod n; inc(len); for i:=0 to n-1 do if (i=0) or (long[i]>0) and (long[i]<len) then begin k:=i+r; if k>=n then k:=k-n; if long[k]=0 then begin long[k]:=len; father[k]:=i; end; end; end; k:=father[0]; tmpf:=k; tmpl:=len; father[0]:=-1; long[0]:=0; r:=0; flag:=true; while k>=0 do begin r:=r*10+1; if r div n>0 then begin write(r div n); flag:=false; end; if (r div n=0)and(flag=false) then write(0); r:=r mod n; for i:=len-1 downto long[k]+1 do begin r:=r*10; if r div n>0 then begin write(r div n); flag:=false; end; if (r div n=0)and(flag=false) then write(0); r:=r mod n; end; len:=long[k]; k:=father[k]; end; write(' '); k:=tmpf; len:=tmpl; father[0]:=-1; long[0]:=0; while k>=0 do begin write(1); for i:=len-1 downto long[k]+1 do write(0); len:=long[k]; k:=father[k]; end; end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533539.html
