Cod sursa(job #115741)
Utilizator | Bogdan-Alexandru Stoica fireatmyself | Data | 16 decembrie 2007 21:33:21 |
---|---|---|---|
Problema | Multiplu | Scor | 0 |
Compilator | c | Status | done |
Runda | Arhiva de probleme | Marime | 6.93 kb |
#include <stdio.h>
int gcd(int a, int b)
{
if (!b) return a;
else return gcd(b, a%b);
}
int A, B, X[11], Sol[10011], C[11][11], rez[10011], Ans[10011];
int main()
{
int i, j, g, nx=0, nsol=0, nr=0, curr=0, ok, c, c2, t, nans = 10000, k;
long long nrr;
freopen("multiplu.in", "r", stdin);
scanf("%d%d", &A, &B);
g = A*B/gcd(A,B);
for (i = 1; i < 20000000; i++)
{
nrr = (long long)i*(long long)g;
while (nrr)
{
if ( (nrr%10) > 1 ) break;
nrr /= 10;
}
if (nrr==0)
{
freopen("multiplu.out", "w", stdout);
nrr = (long long)i*(long long)g;
printf("%lld\n", nrr);
return 0;
}
} */
while (g)
{
X[nx++] = g%10;
g /= 10;
}
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++) C[i][j] = (i*j)%10;
for (c = 9; c >= 0; c--)
{
memset(Sol,0,sizeof(Sol));
memset(rez,0,sizeof(rez));
curr = 0; nr = nsol = 0;
if (C[c][X[0]]<2)
{
for (i = t = 0; i < nx; i++) rez[i] = X[i];
for (i = t = 0; i < nx || t; i++, t /= 10)
rez[i] = (t+=(rez[i]*c))%10;
nr = i;
for (i = t = 0; i < nr || i < nx || t; i++, t/=10)
Sol[i] = (t+=(Sol[i]+rez[i]))%10;
nsol = i;
for (i = 0; i < nsol; i++)
if (Sol[i]>1) break;
if (i==nsol&&c>0)
{
if (nsol<nans)
{
for (i = 0; i < nans; i++) Ans[i] = Sol[i];
nans = nsol;
}
else
if (nsol==nans)
{
i = nsol-1;
while (Ans[i]==Sol[i]&&i>0) i--;
if (Ans[i]>Sol[i])
for (i = 0; i < nans; i++) Ans[i] = Sol[i];
}
break; }
while (1)
{
if (nsol>100) break;
for (c2 = 1, ok = 0; c2 < 10; c2++)
if (((C[c2][X[0]]+Sol[curr+1])%10)<2)
{
memset(rez,0,sizeof(rez));
for (i = 0; i < nx; i++) rez[i+curr+1] = X[i];
nr = nx+curr+2;
for (i = t = 0; i < nr || t; i++, t /= 10)
rez[i] = (t+=(rez[i]*c2))%10;
nr = i;
for (i = t = 0; i < nr || i < nsol || t; i++, t/=10)
Sol[i] = (t+=(Sol[i]+rez[i]))%10;
nsol = i;
curr++; ok = 1; break;
}
if (!ok) break;
if (c2==0) {
for (c2 = 9, ok = 0; c2 >= 0; c2--)
if (((C[c2][X[0]]+Sol[curr+1])%10)<2)
{
memset(rez,0,sizeof(rez));
for (i = 0; i < nx; i++) rez[i+curr+1] = X[i];
nr = nx+curr+2;
for (i = t = 0; i < nr || t; i++, t /= 10)
rez[i] = (t+=(rez[i]*c2))%10;
nr = i;
for (i = t = 0; i < nr || i < nsol || t; i++, t/=10)
Sol[i] = (t+=(Sol[i]+rez[i]))%10;
nsol = i;
curr++; ok = 1; break;
}
}
for (i = 0; i < nsol; i++)
if (Sol[i]>1) break;
if (i==nsol)
{
if (nsol<nans)
{
for (i = 0; i < nans; i++) Ans[i] = Sol[i];
nans = nsol;
}
else
if (nsol==nans)
{
i = nsol-1;
while (Ans[i]==Sol[i]&&i>0) i--;
if (Ans[i]>Sol[i])
for (i = 0; i < nans; i++) Ans[i] = Sol[i];
}
break; }
}
}
}
if (nans==10000) {
nr = 1<<22;
for (k = 4; k < nr; k++)
{
nans = 0;
for (j = 0; j < 24; j++)
Ans[nans++] = ( (k>>j)&1 );
for (i = 0; i < 10000; i++) rez[i] = Ans[i];
while (rez[nans]==0) nans--;
for (i = nans, t = 0; i >= 0; i--, t%=A)
rez[i] = ( t = (t*10+rez[i]) )/A;
if (t>0) continue;
for (i = 0; i <= nans; i++) rez[i] = Ans[i];
for (i = nans, t = 0; i >= 0; i--, t%=B)
rez[i] = ( t = (t*10+rez[i]) )/B;
if (t>0) continue;
nans++;
break;
} }
freopen("multiplu.out", "w", stdout);
for (i = nans-1; i >= 0; i--) printf("%d", Ans[i]);
printf("\n");
return 0;
}