Pagini recente » Cod sursa (job #1113616) | Cod sursa (job #2294883) | Cod sursa (job #264089) | Cod sursa (job #859997) | Cod sursa (job #115325)
Cod sursa(job #115325)
#include<stdio.h>
#include<string.h>
long long int a,b,nz,nz1,aux,m,m0[20],m1[20],i,j,lc,lf;
char c0[10][20],c1[10][20],sc[10000000],sf[10000000];
void back(long long int poz);
void versol();
void ad(char *s1,char *s2);
void subs(char *s1,char *s2);
int main()
{
FILE *f,*g;f=fopen("multiplu.in","r");g=fopen("multiplu.out","w");
fscanf(f,"%lld%lld",&a,&b);
while(a%2==0){nz1++;a/=2;}nz=(nz>nz1)?nz:nz1;nz1=0;
while(a%5==0){nz1++;a/=5;}nz=(nz>nz1)?nz:nz1;nz1=0;
while(b%2==0){nz1++;b/=2;}nz=(nz>nz1)?nz:nz1;nz1=0;
while(b%5==0){nz1++;b/=5;}nz=(nz>nz1)?nz:nz1;
m=a*b;lf=10000000;
while(b){a=a%b;aux=a;a=b;b=aux;}
m/=a;
for(i=0;i<=9;i++) m0[i]=m*i;
for(i=0;i<=8;i++)
{ for(j=i;j<=9;j++)
if((i+m0[j])%10==0)break;
aux=m0[i];m0[i]=m0[j];m0[j]=aux;
}
for(i=0;i<=9;i++)
{ j=0;while(m0[i]){c0[i][j]='0'+(char)(m0[i]%10);m0[i]/=10;j++;}}
c0[0][0]='0';
for(i=0;i<=9;i++) m1[i]=m*i;
for(i=0;i<=8;i++)
{ for(j=i;j<=9;j++)
if((i+m1[j])%10==1)break;
aux=m1[i];m1[i]=m1[j];m1[j]=aux;
}
for(i=0;i<=9;i++)
{ j=0;while(m1[i]){c1[i][j]='0'+(char)(m1[i]%10);m1[i]/=10;j++;}}
c1[1][0]='0';
strcpy(sc,c1[0]);
back(0);
for(i=lf-1;i>=0;i--)
fprintf(g,"%c",sf[i]);
for(i=1;i<=nz;i++)
fprintf(g,"0");
fprintf(g,"\n");
fcloseall();
return 0;
}
void back(long long int poz)
{ char *qq,cc;
long long int ok=1,v;
if(strlen(sc)>lf)return;
qq=&sc[poz];
for(cc='2';cc<='9';cc++)
if(strchr(qq,cc)){ok=0;break;}
if(ok){versol();return;}
v=(long long int)(sc[poz]-'0');
ad(qq,c1[v]);if(strlen(sc)<=lf)back(poz+1);subs(qq,c1[v]);
ad(qq,c0[v]);if(strlen(sc)<=lf)back(poz+1);subs(qq,c0[v]);
}
void ad(char *s1,char *s2)
{ long long int ii;
for(ii=0;;ii++)
{ if(!s2[ii]) break;
s1[ii]+=s2[ii]-'0';
if(s2[ii]<'0')s2[ii]+='0';
}
for(ii=0;;ii++)
{ while(s1[ii]>'9'){s1[ii]-=10;s1[ii+1]+=1;}
if(!s1[ii+1])break;
if(s1[ii+1]<'0')s1[ii+1]+='0';
}
}
void subs(char *s1,char *s2)
{ long long int ii;
for(ii=0;;ii++)
{ if(!s2[ii]) break;
s1[ii]-=s2[ii]-'0';
}
for(ii=0;;ii++)
{ if(!s1[ii])break;
while(s1[ii]<'0'){s1[ii]+=10;s1[ii+1]-=1;}
}
while(s1[ii]<='0'){s1[ii]=0;ii--;}
}
void versol()
{ long long int ok;
lc=strlen(sc);
if(lc>lf)return;
if(lc<lf){lf=lc;strcpy(sf,sc);return;}
ok=0;
for(i=lf;i>=0;i--)
{ if(sc[i]>sf[i])break;
if(sc[i]<sf[i]){ok=1;break;}
}
if(ok) strcpy(sf,sc);
}