Mai intai trebuie sa te autentifici.
Cod sursa(job #1901079)
| Utilizator | Data | 3 martie 2017 18:51:49 | |
|---|---|---|---|
| Problema | Multiplu | Scor | 70 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 1.45 kb |
#include<bits/stdc++.h>
using namespace std;
int dv,a,b,m,q[3800005],pre[3800005],st,dr,nr,rest1,rest2;
bool seen[3800005],v[3800005],cif[3800005];
int cmmmc(int a,int b)
{
int x=a,y=b;
int r=a%b;
while(r)
{
a=b;b=r;
r=a%b;
}
return (x*y/b);
}
void BuildSol(int dr)
{
while(dr>=1)
{
v[++dv]=cif[dr];
dr=pre[dr];
}
}
void afisare()
{
for(int i=dv;i>=1;i--) printf("%d",v[i]);
printf("\n");
}
int main()
{
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
scanf("%d%d",&a,&b);
m=cmmmc(a,b);
cif[1]=1;
q[1]=1;
seen[1]=1;
st=1;
dr=2;
while(st<dr)
{
nr=q[st];
rest1=(10*nr)%m;
rest2=(10*nr+1)%m;
if(!seen[rest1])
{
q[dr]=rest1;
seen[rest1]=1;
cif[dr]=0;
pre[dr]=st;
if(!q[dr])
{
BuildSol(dr);
afisare();
return 0;
}
dr++;
}
if(!seen[rest2])
{
q[dr]=rest2;
seen[rest2]=1;
cif[dr]=1;
pre[dr]=st;
if(!q[dr])
{
BuildSol(dr);
afisare();
return 0;
}
dr++;
}
seen[q[st]]=0;
st++;
}
return 0;
}
