Pagini recente » Cod sursa (job #2786140) | Cod sursa (job #1060169) | Cod sursa (job #311997) | Cod sursa (job #2802856) | Cod sursa (job #1878631)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
vector <bool>v;
queue <int>Q;
const int Nmax=2000000+5;
int dp[Nmax];
bool cif[Nmax];
int a,b,c;
void bfs()
{
int r;
r=Q.front();
Q.pop();
if((r*10)%c==0)
{
dp[0]=r;
cif[0]=0;
return;
}
else
{
if(dp[(r*10)%c]==0){
Q.push((r*10)%c);
dp[(r*10)%c]=r;
cif[(r*10)%c]=0;
}
}
if((r*10+1)%c==0)
{
dp[0]=r;
cif[0]=1;
return;
}
else
{
if(dp[(r*10+1)%c]==0){
Q.push((r*10+1)%c);
dp[(r*10+1)%c]=r;
cif[(r*10+1)%c]=1;
}
}
bfs();
}
int cmmdc(int x,int y)
{
int r;
while(y!=0)
{
r=x%y;
x=y;
y=r;
}
return x;
}
int main()
{
fin>>a>>b;
c=(a*b)/cmmdc(a,b);
Q.push(1);
bfs();
int r=0;
while(r!=1)
{
v.push_back(cif[r]);
r=dp[r];
}
v.push_back(1);
for(int i=v.size()-1;i>=0;--i)fout<<v[i];
return 0;
}