Pagini recente » Cod sursa (job #860883) | Cod sursa (job #1949958) | Cod sursa (job #2339095) | Cod sursa (job #1667947) | Cod sursa (job #679098)
Cod sursa(job #679098)
#include <fstream>
#include <cstring>
#define maxN 2000001
using namespace std;
ifstream in;
ofstream out;
struct queue
{
int rest,cif,nod;
}q[maxN];
int r[maxN];
inline int eucl(int a,int b)
{
if(b==0) return a;
for(int r=a%b;b;r=a%b,a=b,b=r);
return a;
}
inline void print(int nod)
{
if(q[nod].nod==0)
{
out<<'1';
return;
}
print(q[nod].nod);
out<<q[nod].cif;
}
int main()
{
int A,B,mod;
in.open("multiplu.in");
in>>A>>B;
in.close();
mod=eucl(A,B);
mod=((long long)A*B)/mod;
out.open("multiplu.out");
memset(r,0,sizeof(r));
q[1].rest=1;
q[1].cif=1;
q[1].nod=0;
int head,tail;
head=tail=1;
while(head<=tail)
{
int rest=q[head].rest;
rest*=10;
rest%=mod;
if(r[rest]==0)
{
r[rest]=1;
q[++tail].rest=rest;
q[tail].cif=0;
q[tail].nod=head;
}
if(rest==0)
{
print(tail);
break;
}
++rest;
rest%=mod;
if(r[rest]==0)
{
r[rest]=1;
q[++tail].rest=rest;
q[tail].cif=1;
q[tail].nod=head;
}
if(rest==0)
{
print(tail);
break;
}
head++;
}
out<<'\n';
out.close();
return 0;
}