#include <stdio.h> #include <stdlib.h> #include <string.h> char s1[16]="0123456789ABCDEF";//auxiliar strings char s2[16]="0123456789abcdef"; int num(char c,int p)//return the value of the digit { int i=0; while (i<p) { if ((s1[i]==c) || (s2[i]==c)) { return i; } i++; } return -1; } void insert(char c,char* s,int k) { int i; for (i=strlen(s)+1;i>=k+1;i--) { s[i]=s[i-1]; } s[i]=c; } void cut_0(char *s)//cuts the zeroes from the left side { while ((s[0]=='0') && (strlen(s)!=1)) { int j; for (j=0;j<=strlen(s)-1;j++) { s[j]=s[j+1]; } } } void addition(char* a,char* b,char* c,int p) { int carry=0; int k=strlen(a)-1,l=strlen(b)-1; while ((k>=0) && (l>=0))//while both number are digit on the current poisition { insert(s1[(num(a[k],p)+num(b[l],p)+carry)%p],c,0);//insert on the first position the suitable digit carry=(num(a[k],p)+num(b[l],p)+carry)/p; k--; l--; } if ((k<0) && (l>=0))//if the second number has more digits than the first one { while (l>=0) { insert(s1[(num(b[l],p)+carry)%p],c,0); carry=(num(b[l],p)+carry)/p; l--; } } else if ((k>=0) && (l<0))//if the first number has more digits than the firt one { while (k>=0) { insert(s1[(num(a[k],p)+carry)%p],c,0); carry=(num(a[k],p)+carry)/p; k--; } } if (carry==1)//if exists carry then inserts it { insert('1',c,0); } } void subtraction(char* a,char* b,char* c,int p,int *neg) { if ((strlen(a)<strlen(b)) || (strlen(a)==strlen(b)))//if the minuend is less than the subtrahend the reverse the numbers and the result will be negative { int q=1; if (strlen(a)==strlen(b)) { int i=0; while ((a[i]==b[i]) && (i+1!=strlen(a))) { i++; } if ((i!=strlen(a)) && (a[i]<b[i])) { q=1; } else { q=0; } } if (q==1) { char temp[100]; int i; for (i=0;i<=strlen(a);i++) { temp[i]=a[i]; } for (i=0;i<=strlen(b);i++) { a[i]=b[i]; } for (i=0;i<=strlen(temp);i++) { b[i]=temp[i]; } *neg=1; } } int carry=0; int k=strlen(a)-1,l=strlen(b)-1; while ((k>=0) && (l>=0))//while both number has digit in the current position { if (num(a[k],p)-num(b[l],p)+carry>=0) { insert(s1[num(a[k],p)-num(b[l],p)+carry],c,0); carry=0; } else { insert(s1[num(a[k],p)-num(b[l],p)+carry+p],c,0); carry=-1; } k--; l--; } if ((k>=0) && (l<0))//if the minuend has more digits { while (k>=0) { if (num(a[k],p)+carry>=0) { insert(s1[num(a[k],p)+carry],c,0); carry=0; } else { insert(s1[num(a[k],p)+carry+p],c,0); carry=-1; } k--; } } cut_0(c); } void multiplication(char *a,char* b,char *c,int p) { int i; for (i=strlen(b)-1;i>=0;i--)//for every digits from the second number will be executed the multiplication { char temp[strlen(a)+strlen(b)]; temp[0]='\0'; int carry=0,j; for (j=0;j<strlen(b)-1-i;j++)//more and more zeroes have to wil be on the right side of the subresults of multiplication { insert('0',temp,0); } for (j=strlen(a)-1;j>=0;j--) { insert(s1[(num(b[i],p)*num(a[j],p)+carry)%p],temp,0); carry=(num(b[i],p)*num(a[j],p)+carry)/p; } char d[200]; d[0]='\0'; insert((char)carry+'0',temp,0); addition(temp,c,d,p);//addition of the subresult for (j=0;j<=strlen(d);j++) { c[j]=d[j]; } } cut_0(c); } void division(char* a,char* b,char* q,char *r,int p) { int i,carry=0; for (i=0;i<strlen(a);i++)//for every digit of the dividend { insert(s1[(carry*p+num(a[i],p))/num(b[0],p)],q,strlen(q)); carry=(carry*p+num(a[i],p))%num(b[0],p); } *r=s1[carry]; cut_0(q); } void conversion(char* a,int p,int q) { if (p>q)//if p>q then the used algorithm is the successive division by the destination base { char b[100]; b[0]='\0'; if ((a[0]=='0') && (a[1]=='\0')) { b[0]='0'; b[1]='\0'; } while ((a[0]!='0') || (a[1]!='\0'))//while the dividend is not zero { char quo[100],rem; quo[0]='\0'; division(a,&s1[q],quo,&rem,p); insert(rem,b,0); int i; for (i=0;i<=strlen(quo);i++) { a[i]=quo[i]; } } int i; for (i=0;i<=strlen(b);i++) { a[i]=b[i]; } } else if (p<q)//if p<q then the used algorithm is the substitution method { char b[100]; b[0]='0'; b[1]='\0'; int i=0; while (i<strlen(a))//the algorithm is used for every digit from the number { char res[100]; res[0]=a[i]; res[1]='\0'; int j; for (j=1;j<=strlen(a)-i-1;j++)//multiplication of current digit with the suitable power of the base p { char temp[100]; temp[0]='\0'; char c[2]; c[0]=s1[p]; c[1]='\0'; multiplication(res,&c,temp,q); int k; for (k=0;k<=strlen(temp);k++) { res[k]=temp[k]; } } char temp[100]; temp[0]='\0'; addition(b,res,temp,q); for (j=0;j<=strlen(temp);j++) { b[j]=temp[j]; } i++; } for (i=0;i<=strlen(b);i++) { a[i]=b[i]; } } cut_0(a); } void rap_conv(char* a,int p,int q) { if (p!=2)//if the source base is not 2 then it will be converted in base 2 { char b[100]; b[0]='\0'; int gr; switch (p) { case 4: gr=2; break; case 8: gr=3; break; case 16: gr=4; break; } int i; for (i=strlen(a)-1;i>=0;i--)//convert digit by digit to base 2 { char temp[5]; temp[0]=a[i]; temp[1]='\0'; conversion(temp,p,2); int j; int k=strlen(temp); for (j=1;j<=gr-k;j++) { insert('0',temp,0); } for (j=gr-1;j>=0;j--) { insert(temp[j],b,0); } } for (i=0;i<=strlen(b);i++) { a[i]=b[i]; } } cut_0(a); if (q!=2) { char b[100]; b[0]='\0'; int gr; switch (q) { case 4: gr=2; break; case 8: gr=3; break; case 16: gr=4; break; } int i; for (i=1;i<=strlen(a)%gr;i++)//if there does not exist enough number of digits then it is completed by zeroes { insert('0',a,0); } for (i=strlen(a)/gr-1;i>=0;i--)//every groups of number containing gr number of digits is converted to the base q { char temp[5]; int j; for (j=i*gr;j<=(i+1)*gr-1;j++) { temp[j-i*gr]=a[j]; } temp[gr]='\0'; conversion(temp,2,q); insert(temp[0],b,0); } for (i=0;i<=strlen(b);i++) { a[i]=b[i]; } } cut_0(a); } int main() { long int t,k,i; scanf("%d %d",&t,&k); long int a[100000]; for (i=0;i<t;i++) { scanf("%d",&a[i]); } for (i=0;i<t;i++) { char s[1000000]; s[0]='\0'; long int j; for (j=0;i<a[i];j++) { long int c; for (c=0;c<k;c++) { insert('0',s,0); } insert('1',s,0); } conversion(s,2,10); char b[7]="666013\0"; char q[100000],r[1000000]; q[0]='\0'; r[0]='\0'; division(s,b,q,r,10); printf("%s\n",r); } return 0; }