Cod sursa(job #1419571)

Utilizator GinguIonutGinguIonut GinguIonut Data 15 aprilie 2015 22:54:57
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int a,b,mc,pr,x,u,p,ok,numar,h,i,aux;
bool frecv[2000001];
int euclid(int a, int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
struct structura
{
    int nr;
    bool caz;
    int parinte;
}dp[2000005];
int main()
{
    fin>>a>>b;
    mc=(a*b)/(euclid(a,b));
    if(1%mc==0)
        fout<<1;
    else
    {
        dp[1].nr=u=p=dp[1].caz=1;
        while(0==0)
        {
            x=dp[p].nr;
            x*=10;
            if(frecv[x%mc]==0)
            {
                dp[++u].nr=x%mc;
                dp[u].parinte=p;
                frecv[x%mc]=1;
                if(x%mc==0)
                {
                    numar=u;
                    break;
                }
            }
            x++;
            if(frecv[x%mc]==0)
            {
                dp[++u].nr=x%mc;
                dp[u].parinte=p;
                frecv[x%mc]=1;
                dp[u].caz=1;
                if(x%mc==0)
                {
                    numar=u;
                    break;
                }
            }
            p++;
        }
        pr=numar;
        while(dp[pr].parinte)
        {
            dp[pr].nr=-1;
            pr=dp[pr].parinte;
        }
        dp[1].nr=-1;
        for(i=1;i<=numar;i++)
            if(dp[i].nr==-1)
                fout<<dp[i].caz;
    }
    return 0;
}