Pagini recente » Cod sursa (job #1479080) | Cod sursa (job #384372) | Cod sursa (job #1244112) | Cod sursa (job #1777217) | Cod sursa (job #3140166)
/*
"TLE is like the wind, always by my side"
- Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cout << #x << " " << x << "\n"
#define debugs(x) cout << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
struct choice
{
int mod;
int lastdigit;
int lastmod;
};
int last[2000001];
int shortestpath[2000001];
bool visited[2000001];
queue<choice> q;
vector<int> ans;
signed main()
{
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a,b,lcm,curr,i;
choice number;
fin >> a >> b;
lcm=(a*b)/__gcd(a,b);
q.push({1,-1,-1});
while (!q.empty())
{
number=q.front();
if (!visited[number.mod])
{
shortestpath[number.mod]=number.lastmod;
last[number.mod]=number.lastdigit;
visited[number.mod]=1;
if (!visited[(number.mod*10)%lcm])
q.push({(number.mod*10)%lcm,0,number.mod});
if (!visited[(number.mod*10+1)%lcm])
q.push({(number.mod*10+1)%lcm,1,number.mod});
}
q.pop();
}
curr=0;
while (shortestpath[curr]!=-1)
{
ans.push_back(last[curr]);
curr=shortestpath[curr];
}
ans.push_back(1);
reverse(ans.begin(),ans.end());
for (i=0; i<ans.size(); i++)
fout << ans[i];
}