// includes #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // macros #define ll long long int #define pb emplace_back #define mk make_pair #define pq priority_queue #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define rep(i, n) FOR(i, 0, n) #define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--) #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) using namespace std; // types typedef pair P; typedef pair Pl; typedef pair Pll; typedef pair Pd; // constants const int inf = 1e9; const ll linf = 1LL << 50; const double EPS = 1e-10; const int mod = 1e9 + 7; // solve template bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;} template bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;} typedef long long Int; const Int B = 10000; // base (power of 10) const int BW = 4; // log B const int MAXDIGIT = 100; // it can represent 4*MAXDIGIT digits (in base 10) struct BigNum { Int digit[MAXDIGIT]; int size; BigNum(int size = 1, Int a = 0) : size(size) { memset(digit, 0, sizeof(digit)); digit[0] = a; } }; const BigNum ZERO(1, 0), ONE(1, 1); // Comparators bool operator<(BigNum x, BigNum y) { if (x.size != y.size) return x.size < y.size; for (int i = x.size-1; i >= 0; --i) if (x.digit[i] != y.digit[i]) return x.digit[i] < y.digit[i]; return false; } bool operator >(BigNum x, BigNum y) { return y < x; } bool operator<=(BigNum x, BigNum y) { return !(y < x); } bool operator>=(BigNum x, BigNum y) { return !(x < y); } bool operator!=(BigNum x, BigNum y) { return x < y || y < x; } bool operator==(BigNum x, BigNum y) { return !(x < y) && !(y < x); } // Utilities BigNum normal(BigNum x) { Int c = 0; for (int i = 0; i < x.size; ++i) { while (x.digit[i] < 0) x.digit[i+1] -= 1, x.digit[i] += B; Int a = x.digit[i] + c; x.digit[i] = a % B; c = a / B; } for (; c > 0; c /= B) x.digit[x.size++] = c % B; while (x.size > 1 && x.digit[x.size-1] == 0) --x.size; return x; } BigNum convert(Int a) { return normal(BigNum(1, a)); } BigNum convert(const string &s) { BigNum x; int i = s.size() % BW; if (i > 0) i -= BW; for (; i < (int)s.size(); i += BW) { Int a = 0; for (int j = 0; j < BW; ++j) a = 10 * a + (i + j >= 0 ? s[i+j] - '0' : 0); x.digit[x.size++] = a; } reverse(x.digit, x.digit+x.size); return normal(x); } // Input/Output ostream &operator<<(ostream &os, BigNum x) { os << x.digit[x.size-1]; for (int i = x.size-2; i >= 0; --i) os << setw(BW) << setfill('0') << x.digit[i]; return os; } istream &operator>>(istream &is, BigNum &x) { string s; is >> s; x = convert(s); return is; } // Basic Operations BigNum operator+(BigNum x, BigNum y) { if (x.size < y.size) x.size = y.size; for (int i = 0; i < y.size; ++i) x.digit[i] += y.digit[i]; return normal(x); } BigNum operator-(BigNum x, BigNum y) { assert(x >= y); for (int i = 0; i < y.size; ++i) x.digit[i] -= y.digit[i]; return normal(x); } BigNum operator*(BigNum x, BigNum y) { BigNum z(x.size + y.size); for (int i = 0; i < x.size; ++i) for (int j = 0; j < y.size; ++j) z.digit[i+j] += x.digit[i] * y.digit[j]; return normal(z); } BigNum operator*(BigNum x, Int a) { for (int i = 0; i < x.size; ++i) x.digit[i] *= a; return normal(x); } pair divmod(BigNum x, Int a) { Int c = 0, t; for (int i = x.size-1; i >= 0; --i) { t = B * c + x.digit[i]; x.digit[i] = t / a; c = t % a; } return pair(normal(x), c); } BigNum operator/(BigNum x, Int a) { return divmod(x, a).first; } Int operator%(BigNum x, Int a) { return divmod(x, a).second; } pair divmod(BigNum x, BigNum y) { if (x.size < y.size) return pair(ZERO, x); int F = B / (y.digit[y.size-1] + 1); // multiplying good-factor x = x * F; y = y * F; BigNum z(x.size - y.size + 1); for (int k = z.size-1, i = x.size-1; k >= 0; --k, --i) { z.digit[k] = (i+1 < x.size ? x.digit[i+1] : 0) * B + x.digit[i]; z.digit[k] /= y.digit[y.size-1]; BigNum t(k + y.size); for (int m = 0; m < y.size; ++m) t.digit[k+m] = z.digit[k] * y.digit[m]; t = normal(t); while (x < t) { z.digit[k] -= 1; for (int m = 0; m < y.size; ++m) t.digit[k+m] -= y.digit[m]; t = normal(t); } x = x - t; } return pair(normal(z), x / F); } BigNum operator/(BigNum x, BigNum y) { return divmod(x, y).first; } BigNum operator%(BigNum x, BigNum y) { return divmod(x, y).second; } // Advanced Operations BigNum shift(BigNum x, int k) { if (x.size == 1 && x.digit[0] == 0) return x; x.size += k; for (int i = x.size - 1; i >= k; --i) x.digit[i] = x.digit[i-k]; for (int i = k-1; i >= 0; --i) x.digit[i] = 0; return x; } BigNum sqrt(BigNum x) { // verified UVA 10023 const BigNum _20 = convert(2*B); BigNum odd = ZERO; BigNum rem(2,0); BigNum ans = ZERO; for (int i = 2*((x.size-1)/2); i >= 0; i -= 2) { int group = (i+1 < x.size ? x.digit[i+1] : 0) * B + x.digit[i]; odd = _20 * ans + ONE; rem = shift(rem, 2) + convert(group); int count = 0; while (rem >= odd) { count = count + 1; rem = rem - odd; odd.digit[0] += 2; odd = normal(odd); } ans = shift(ans,1) + convert(count); } return ans; } BigNum gcd(BigNum a, BigNum b) { if(a > b)return gcd(b, a); if(a == ZERO)return b; return gcd(b % a, a); } int main(int argc, char const* argv[]) { ios_base::sync_with_stdio(false); cin.tie(0); BigNum N, M; ll n, m; cin >> n >> m; N = convert(n); M = convert(m); BigNum g = gcd(N, M); g = M / g; int t = 0; while(g % 2 == 0){ g = g / 2; t++; } int tt = 0; while(g % 5 == 0){ g = g / 5; tt++; } t = max(t, tt); if(g != ONE)cout << -1 << endl; else{ rep(i, t)N = N * 10; BigNum T = N / M; while(T % 10 == 0)T = T / 10; cout << T % 10 << endl; } return 0; }