Pagini recente » Cod sursa (job #1645959) | Cod sursa (job #2081430) | Cod sursa (job #1947646) | Cod sursa (job #1758191) | Cod sursa (job #743724)
Cod sursa(job #743724)
#include<iostream>
#include<fstream>
using namespace std;
char viz[2000010];
struct queue
{
char c;
int prev,r;
};
queue q[2000010];
char sol[2000010];
int main()
{
int p,u,cmmdc,a,b,m,ca,cb,r1,lsol=0;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
f>>a>>b;
f.close();
ca=a;
cb=b;
while(cb!=0)
{
r1=ca%cb;
ca=cb;
cb=r1;
}
cmmdc=ca;
m=a*b/cmmdc;
p=1;u=1;
q[1].r=1;q[1].prev=0;
q[1].c=1;viz[1]=1;
while(p<=u)
{
r1=(q[p].r*10)%m;
if(viz[r1]==0)
{
viz[r1]++;
u++;
q[u].r=r1;
q[u].prev=p;
q[u].c=0;
if(r1==0)
break;
}
r1=(q[p].r*10+1)%m;
if(viz[r1]==0)
{
viz[r1]++;
u++;
q[u].r=r1;
q[u].prev=p;
q[u].c=1;
if(r1==0)
break;
}
p++;
}
while(u>0)
{
sol[++lsol]=q[u].c;
u=q[u].prev;
}
for(int i=lsol;i>0;i--)
g<<(int)sol[i];
g.close();
}