Cod sursa(job #115741)

Utilizator fireatmyselfBogdan-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;

}