POJ 1426 Find The Multiple (神奇的打表da法）
Description
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input
2 6 19 0
Sample Output
10 100100100100100100 111111111111111111
简单意思是给你一个200以内的正数，问你是否有一串以0，1组成的十进制数字，使得这串数字是该正数的倍数
我知道这是一道搜索题目，但是我还是想用打表的方法来试一下。
具体的思路就是不断枚举一个整数，将该整数的二进制形式转换为十进制，再判断是否可以整除。
但是我看到最大是100位数，便犹豫了一下。
2的100次方是多少呀？
百度了一下，答案是1.2*10^30.
可以参考这个问题
额妹嘤！
但是我经过简单思考然后加上我的直觉后认为，肯定不会运算到2的100次方。因为只有1-200这200个数字，应该会在一个比较小的位数就停止下来。
然后我就写了打表的算法，顺便复习了一下c++的高精度和10进制数转换成2进制数的一些知识。
这是打表的算法
#include<iostream>
#include<cstring>
using namespace std;
int a[103];
int b[201][100];
int blen[201];
int len;
int divide(int x){
int an=0;
for(int i=len-1;i>=0;i--){
if(a[i]+an*10<x){
an=a[i]+an*10;
continue;
}
an=(a[i]+an*10)%x;
}
if(an==0){
return 1;
}
return 0;
}
int setto(int n){
int num=0;
while(n!=0){
if(n%2)
a[num++]=1;
else
a[num++]=0;
n=n/2;
}
return num;
}
void printt(int n){
cout<<n<<" ";
blen[n]=len;
for(int i=len-1;i>=0;i--){
cout<<a[i];
b[n][i]=a[i];
}
cout<<endl;
}
void printtt(int n){
for(int i=blen[n]-1;i>=0;i--){
cout<<b[n][i];
}
cout<<endl;
}
int main(){
for(int i=1;i<=200;i++){
for(int tem=1;tem<=1000000000;tem++){
memset(a,0,sizeof(a));
len=setto(tem);
if(divide(i)){
printt(i);
break;
}
}
}
return 0;
}然后运行之后发现速度竟然这么快！最大的数字也仅有19位数！
我可以试着保存在一个2维数组里面直接提交POJ。
结果是TLE。。。。。
看来还是得打表
这是第一次打表后的代码
#include<iostream>
using namespace std;
int main(){
int x;
while(cin>>x&&x!=0){
if(x==1){
cout<<"1"<<endl;
}
if(x==2){
cout<<"10"<<endl;
}
if(x==3){
cout<<"111"<<endl;
}
if(x==4){
cout<<"100"<<endl;
}
if(x==5){
cout<<"10"<<endl;
}
if(x==6){
cout<<"1110"<<endl;
}
if(x==7){
cout<<"1001"<<endl;
}
if(x==8){
cout<<"1000"<<endl;
}
if(x==9){
cout<<"111111111"<<endl;
}
if(x==10){
cout<<"10"<<endl;
}
if(x==11){
cout<<"11"<<endl;
}
if(x==12){
cout<<"11100"<<endl;
}
if(x==13){
cout<<"1001"<<endl;
}
if(x==14){
cout<<"10010"<<endl;
}
if(x==15){
cout<<"1110"<<endl;
}
if(x==16){
cout<<"10000"<<endl;
}
if(x==17){
cout<<"11101"<<endl;
}
if(x==18){
cout<<"1111111110"<<endl;
}
if(x==19){
cout<<"11001"<<endl;
}
if(x==20){
cout<<"100"<<endl;
}
if(x==21){
cout<<"10101"<<endl;
}
if(x==22){
cout<<"110"<<endl;
}
if(x==23){
cout<<"110101"<<endl;
}
if(x==24){
cout<<"111000"<<endl;
}
if(x==25){
cout<<"100"<<endl;
}
if(x==26){
cout<<"10010"<<endl;
}
if(x==27){
cout<<"1101111111"<<endl;
}
if(x==28){
cout<<"100100"<<endl;
}
if(x==29){
cout<<"1101101"<<endl;
}
if(x==30){
cout<<"1110"<<endl;
}
if(x==31){
cout<<"111011"<<endl;
}
if(x==32){
cout<<"100000"<<endl;
}
if(x==33){
cout<<"111111"<<endl;
}
if(x==34){
cout<<"111010"<<endl;
}
if(x==35){
cout<<"10010"<<endl;
}
if(x==36){
cout<<"11111111100"<<endl;
}
if(x==37){
cout<<"111"<<endl;
}
if(x==38){
cout<<"110010"<<endl;
}
if(x==39){
cout<<"10101"<<endl;
}
if(x==40){
cout<<"1000"<<endl;
}
if(x==41){
cout<<"11111"<<endl;
}
if(x==42){
cout<<"101010"<<endl;
}
if(x==43){
cout<<"1101101"<<endl;
}
if(x==44){
cout<<"1100"<<endl;
}
if(x==45){
cout<<"1111111110"<<endl;
}
if(x==46){
cout<<"1101010"<<endl;
}
if(x==47){
cout<<"10011"<<endl;
}
if(x==48){
cout<<"1110000"<<endl;
}
if(x==49){
cout<<"1100001"<<endl;
}
if(x==50){
cout<<"100"<<endl;
}
if(x==51){
cout<<"100011"<<endl;
}
if(x==52){
cout<<"100100"<<endl;
}
if(x==53){
cout<<"100011"<<endl;
}
if(x==54){
cout<<"11011111110"<<endl;
}
if(x==55){
cout<<"110"<<endl;
}
if(x==56){
cout<<"1001000"<<endl;
}
if(x==57){
cout<<"11001"<<endl;
}
if(x==58){
cout<<"11011010"<<endl;
}
if(x==59){
cout<<"11011111"<<endl;
}
if(x==60){
cout<<"11100"<<endl;
}
if(x==61){
cout<<"100101"<<endl;
}
if(x==62){
cout<<"1110110"<<endl;
}
if(x==63){
cout<<"1111011111"<<endl;
}
if(x==64){
cout<<"1000000"<<endl;
}
if(x==65){
cout<<"10010"<<endl;
}
if(x==66){
cout<<"1111110"<<endl;
}
if(x==67){
cout<<"1101011"<<endl;
}
if(x==68){
cout<<"1110100"<<endl;
}
if(x==69){
cout<<"10000101"<<endl;
}
if(x==70){
cout<<"10010"<<endl;
}
if(x==71){
cout<<"10011"<<endl;
}
if(x==72){
cout<<"111111111000"<<endl;
}
if(x==73){
cout<<"10001"<<endl;
}
if(x==74){
cout<<"1110"<<endl;
}
if(x==75){
cout<<"11100"<<endl;
}
if(x==76){
cout<<"1100100"<<endl;
}
if(x==77){
cout<<"1001"<<endl;
}
if(x==78){
cout<<"101010"<<endl;
}
if(x==79){
cout<<"10010011"<<endl;
}
if(x==80){
cout<<"10000"<<endl;
}
if(x==81){
cout<<"1111111101"<<endl;
}
if(x==82){
cout<<"111110"<<endl;
}
if(x==83){
cout<<"101011"<<endl;
}
if(x==84){
cout<<"1010100"<<endl;
}
if(x==85){
cout<<"111010"<<endl;
}
if(x==86){
cout<<"11011010"<<endl;
}
if(x==87){
cout<<"11010111"<<endl;
}
if(x==88){
cout<<"11000"<<endl;
}
if(x==89){
cout<<"11010101"<<endl;
}
if(x==90){
cout<<"1111111110"<<endl;
}
if(x==91){
cout<<"1001"<<endl;
}
if(x==92){
cout<<"11010100"<<endl;
}
if(x==93){
cout<<"10000011"<<endl;
}
if(x==94){
cout<<"100110"<<endl;
}
if(x==95){
cout<<"110010"<<endl;
}
if(x==96){
cout<<"11100000"<<endl;
}
if(x==97){
cout<<"11100001"<<endl;
}
if(x==98){
cout<<"11000010"<<endl;
}
if(x==99){
cout<<"111111111111111111"<<endl;
}
if(x==100){
cout<<"100"<<endl;
}
if(x==101){
cout<<"101"<<endl;
}
if(x==102){
cout<<"1000110"<<endl;
}
if(x==103){
cout<<"11100001"<<endl;
}
if(x==104){
cout<<"1001000"<<endl;
}
if(x==105){
cout<<"101010"<<endl;
}
if(x==106){
cout<<"1000110"<<endl;
}
if(x==107){
cout<<"100010011"<<endl;
}
if(x==108){
cout<<"110111111100"<<endl;
}
if(x==109){
cout<<"1001010111"<<endl;
}
if(x==110){
cout<<"110"<<endl;
}
if(x==111){
cout<<"111"<<endl;
}
if(x==112){
cout<<"10010000"<<endl;
}
if(x==113){
cout<<"1011011"<<endl;
}
if(x==114){
cout<<"110010"<<endl;
}
if(x==115){
cout<<"1101010"<<endl;
}
if(x==116){
cout<<"110110100"<<endl;
}
if(x==117){
cout<<"10101111111"<<endl;
}
if(x==118){
cout<<"110111110"<<endl;
}
if(x==119){
cout<<"100111011"<<endl;
}
if(x==120){
cout<<"111000"<<endl;
}
if(x==121){
cout<<"11011"<<endl;
}
if(x==122){
cout<<"1001010"<<endl;
}
if(x==123){
cout<<"10001100111"<<endl;
}
if(x==124){
cout<<"11101100"<<endl;
}
if(x==125){
cout<<"1000"<<endl;
}
if(x==126){
cout<<"11110111110"<<endl;
}
if(x==127){
cout<<"11010011"<<endl;
}
if(x==128){
cout<<"10000000"<<endl;
}
if(x==129){
cout<<"100100001"<<endl;
}
if(x==130){
cout<<"10010"<<endl;
}
if(x==131){
cout<<"101001"<<endl;
}
if(x==132){
cout<<"11111100"<<endl;
}
if(x==133){
cout<<"11101111"<<endl;
}
if(x==134){
cout<<"11010110"<<endl;
}
if(x==135){
cout<<"11011111110"<<endl;
}
if(x==136){
cout<<"11101000"<<endl;
}
if(x==137){
cout<<"10001"<<endl;
}
if(x==138){
cout<<"100001010"<<endl;
}
if(x==139){
cout<<"110110101"<<endl;
}
if(x==140){
cout<<"100100"<<endl;
}
if(x==141){
cout<<"10011"<<endl;
}
if(x==142){
cout<<"100110"<<endl;
}
if(x==143){
cout<<"1001"<<endl;
}
if(x==144){
cout<<"1111111110000"<<endl;
}
if(x==145){
cout<<"11011010"<<endl;
}
if(x==146){
cout<<"100010"<<endl;
}
if(x==147){
cout<<"1100001"<<endl;
}
if(x==148){
cout<<"11100"<<endl;
}
if(x==149){
cout<<"110111"<<endl;
}
if(x==150){
cout<<"11100"<<endl;
}
if(x==151){
cout<<"1110001"<<endl;
}
if(x==152){
cout<<"11001000"<<endl;
}
if(x==153){
cout<<"10111110111"<<endl;
}
if(x==154){
cout<<"10010"<<endl;
}
if(x==155){
cout<<"1110110"<<endl;
}
if(x==156){
cout<<"1010100"<<endl;
}
if(x==157){
cout<<"10101101011"<<endl;
}
if(x==158){
cout<<"100100110"<<endl;
}
if(x==159){
cout<<"100011"<<endl;
}
if(x==160){
cout<<"100000"<<endl;
}
if(x==161){
cout<<"11101111"<<endl;
}
if(x==162){
cout<<"11111111010"<<endl;
}
if(x==163){
cout<<"1010111"<<endl;
}
if(x==164){
cout<<"1111100"<<endl;
}
if(x==165){
cout<<"1111110"<<endl;
}
if(x==166){
cout<<"1010110"<<endl;
}
if(x==167){
cout<<"11111011"<<endl;
}
if(x==168){
cout<<"10101000"<<endl;
}
if(x==169){
cout<<"10111101"<<endl;
}
if(x==170){
cout<<"111010"<<endl;
}
if(x==171){
cout<<"1111011111"<<endl;
}
if(x==172){
cout<<"110110100"<<endl;
}
if(x==173){
cout<<"1011001101"<<endl;
}
if(x==174){
cout<<"110101110"<<endl;
}
if(x==175){
cout<<"100100"<<endl;
}
if(x==176){
cout<<"110000"<<endl;
}
if(x==177){
cout<<"100101111"<<endl;
}
if(x==178){
cout<<"110101010"<<endl;
}
if(x==179){
cout<<"11010111"<<endl;
}
if(x==180){
cout<<"11111111100"<<endl;
}
if(x==181){
cout<<"1001111"<<endl;
}
if(x==182){
cout<<"10010"<<endl;
}
if(x==183){
cout<<"100101"<<endl;
}
if(x==184){
cout<<"110101000"<<endl;
}
if(x==185){
cout<<"1110"<<endl;
}
if(x==186){
cout<<"100000110"<<endl;
}
if(x==187){
cout<<"1001011"<<endl;
}
if(x==188){
cout<<"1001100"<<endl;
}
if(x==189){
cout<<"1010111010111"<<endl;
}
if(x==190){
cout<<"110010"<<endl;
}
if(x==191){
cout<<"11101111"<<endl;
}
if(x==192){
cout<<"111000000"<<endl;
}
if(x==193){
cout<<"11001"<<endl;
}
if(x==194){
cout<<"111000010"<<endl;
}
if(x==195){
cout<<"101010"<<endl;
}
if(x==196){
cout<<"110000100"<<endl;
}
if(x==197){
cout<<"1101000101"<<endl;
}
if(x==198){
cout<<"1111111111111111110"<<endl;
}
if(x==199){
cout<<"111000011"<<endl;
}
if(x==200){
cout<<"1000"<<endl;
}
}
return 0;
}长度竟然高达惊人的7361个字节！
无法想象。
然后想到可以优化一下，把所有的数据拓展到20位，存放在一个大数组里面。这样可以节约下很多个if语句
#include<stdio.h>
char a[4002]="00000000000000000001000000000000000000100000000000000000011100000000000000000100000000000000000000100000000000000000111000000000000000001001000000000000000010000000000000011111111100000000000000000010000000000000000000110000000000000001110000000000000000001001000000000000000100100000000000000000111000000000000000010000000000000000000111010000000000111111111000000000000000011001000000000000000001000000000000000001010100000000000000000110000000000000001101010000000000000011100000000000000000000100000000000000000100100000000000110111111100000000000000100100000000000000011011010000000000000000111000000000000000111011000000000000001000000000000000000011111100000000000000111010000000000000000100100000000001111111110000000000000000000111000000000000001100100000000000000001010100000000000000001000000000000000000111110000000000000010101000000000000001101101000000000000000011000000000000111111111000000000000001101010000000000000000100110000000000000111000000000000000001100001000000000000000001000000000000000010001100000000000000100100000000000000001000110000000001101111111000000000000000000110000000000000010010000000000000000001100100000000000011011010000000000000110111110000000000000001110000000000000000100101000000000000011101100000000000111101111100000000000001000000000000000000000100100000000000000111111000000000000001101011000000000000011101000000000000001000010100000000000000010010000000000000000100110000000011111111100000000000000000010001000000000000000011100000000000000001110000000000000001100100000000000000000010010000000000000010101000000000000010010011000000000000000100000000000000111111110100000000000000111110000000000000001010110000000000000101010000000000000000111010000000000000110110100000000000001101011100000000000000011000000000000000110101010000000000111111111000000000000000001001000000000000110101000000000000001000001100000000000000100110000000000000001100100000000000001110000000000000000011100001000000000000110000100011111111111111111100000000000000000100000000000000000001010000000000000100011000000000000011100001000000000000010010000000000000000010101000000000000001000110000000000001000100110000000011011111110000000000001001010111000000000000000001100000000000000000011100000000000010010000000000000000010110110000000000000011001000000000000001101010000000000001101101000000000001010111111100000000000110111110000000000001001110110000000000000011100000000000000000011011000000000000010010100000000001000110011100000000000011101100000000000000000010000000000001111011111000000000000011010011000000000000100000000000000000010010000100000000000000010010000000000000001010010000000000001111110000000000000011101111000000000000110101100000000001101111111000000000000011101000000000000000000100010000000000010000101000000000000110110101000000000000001001000000000000000001001100000000000000100110000000000000000010010000000111111111000000000000000011011010000000000000001000100000000000000110000100000000000000011100000000000000001101110000000000000001110000000000000001110001000000000000110010000000000001011111011100000000000000010010000000000000011101100000000000000101010000000000010101101011000000000001001001100000000000000010001100000000000000100000000000000000111011110000000001111111101000000000000001010111000000000000011111000000000000000111111000000000000001010110000000000000111110110000000000001010100000000000000010111101000000000000001110100000000000111101111100000000000110110100000000000010110011010000000000011010111000000000000000100100000000000000001100000000000000010010111100000000000110101010000000000000110101110000000001111111110000000000000001001111000000000000000100100000000000000010010100000000000110101000000000000000000011100000000000010000011000000000000001001011000000000000010011000000000101011101011100000000000000110010000000000000111011110000000000011100000000000000000000011001000000000001110000100000000000000010101000000000000110000100000000000011010001010111111111111111111000000000000111000011000000000000000010000";
int main(){
int x;
while(scanf("%d",&x)&&x){
int y=0;
for(int i=0;i<20;i++){
if(a[(x-1)*20+i]!='0'){
y=i;
break;
}
}
for(int i=y;i<20;i++){
printf("%c",a[(x-1)*20+i]);
}
printf("\n");
}
return 0;
}这样代码数就从7k压缩到了4k，其实还可以再压缩。
#include<stdio.h>
int c[201]={0,1,3,6,9,11,15,19,23,32,34,36,41,45,50,54,59,64,74,79,82,87,90,96,102,105,110,120,126,133,137,143,149,155,161,166,177,180,186,191,195,200,206,213,217,227,234,239,246,253,256,262,268,274,285,288,295,300,308,316,321,327,334,344,351,356,363,370,377,385,390,395,407,412,416,421,428,432,438,446,451,461,467,473,480,486,494,502,507,515,525,529,537,545,551,557,565,573,581,599,602,605,612,620,627,633,640,649,661,671,674,677,685,692,698,705,714,725,734,743,749,754,761,772,780,784,795,803,811,820,825,831,839,847,855,866,874,879,888,897,903,908,914,918,931,939,945,952,957,963,968,975,983,994,999,1006,1013,1024,1033,1039,1045,1053,1064,1071,1078,1085,1092,1100,1108,1116,1122,1132,1141,1151,1160,1166,1172,1181,1190,1198,1209,1216,1221,1227,1236,1240,1249,1256,1263,1276,1282,1290,1299,1304,1313,1319,1328,1338,1357,1366,1370};
char a[1371]={"11011110010111010011000111111111101111100100110010111010000111011111111110110011001010111011010111100010010010110111111110010011011011110111011100000111111111010100101111111110011111001010101100011111101010110110111001111111110110101010011111000011000011001000111001001000111101111111011010010001100111011010110111111110010010111101101111011111100000010010111111011010111110100100001011001010011111111111000100011110111001100100100110101010010011100001111111101111110101011101010011101011011010110101111100011010101111111111010011101010010000011100110110010111000001110000111000010111111111111111111100101100011011100001100100010101010001101000100111101111111001001010111110111100100001011011110010110101011011010010101111111110111110100111011111000110111001010100011001111110110010001111011111011010011100000001001000011001010100111111100111011111101011011011111110111010001000110000101011011010110010010011100110100111111111100001101101010001011000011110011011111100111000111001000101111101111001011101101010100101011010111001001101000111000001110111111111111010101011111111001111110101011011111011101010001011110111101011110111111101101001011001101110101110100100110000100101111110101010110101111111111110010011111001010010111010100011101000001101001011100110010101110101111100101110111111100000011001111000010101010110000100110100010111111111111111111101110000111000"};
int main(){
int x;
while(scanf("%d",&x)&&x){
for(int i=c[x-1];i<c[x];i++){
printf("%c",a[i]);
}
printf("\n");
}
return 0;
}
不需要拓展到20位，只需要保存每一位数字的长度和就可以了
字符串i的长度=c[i]-c[i-1]
这样就成功压缩到2384个字节
