Cod sursa(job #2232284)

Utilizator patcasrarespatcas rares danut patcasrares Data 18 august 2018 14:46:41
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
#include<iostream>
#define DN 2000005
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
long long a,b,r,dp[15][DN],put,pr[15][DN],d[15][DN];
int f,g;
int cmmdc(int a,int b)
{
    int c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
int vf(long long a)
{
    while(a)
    {
        if(a%10>1)
            return 0;
        a=a/10;
    }
    return 1;
}
void ve(int f,int g)
{
    if(d[f][g])
        fout<<1;
    else
        fout<<0;
    if(f==1)
        return;
    return ve(f-1,pr[f][g]);
}
int main()
{
    fin>>a>>b;
    r=(a*b)/cmmdc(a,b);
    dp[0][0]=1;
    put=1;
    for(int i=1;i<=10;i++)
    {
        for(int j=0;j<=r;j++)
        {
            dp[i][j]=dp[i-1][j];
            pr[i][j]=j;
        }
        for(int j=0;j<=r;j++)
        {
            g=(j+put)%r;
            if(g==0)
                g=r;
            if(dp[i-1][j]&&!dp[i][g])
            {
                dp[i][g]=1;
                pr[i][g]=j;
                d[i][g]=1;
            }
        }
        if(dp[i][r]==1)
        {
          //  cout<<i<<' '<<r<<'\n';
            f=i;
            g=r;
            break;
        }
        put=(put*10)%r;
    }
    ve(f,g);
}