【题目描述】
给出一个数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
高精度运算就可以避免了。
vari,n,k,len,r,tmpf,tmpl:longint;flag:boolean;long,father:array[0..10000]of longint;
beginread(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 beginr:=r*10 mod n;inc(len);for i:=0 to n-1 doif (i=0) or (long[i]>0) and (long[i]<len) then begink:=i+r;if k>=n then k:=k-n;if long[k]=0 then beginlong[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 beginr:=r*10+1;if r div n>0 then beginwrite(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 beginr:=r*10;if r div n>0 then beginwrite(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 beginwrite(1);for i:=len-1 downto long[k]+1 do write(0);len:=long[k];k:=father[k];end;
end.
