Editorial for Bedao Grand Contest 08 - EQUAL
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> #define fi first #define se second #define io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; const int MAXN = 1e6 + 7; int mpr[MAXN] = {}; void sieve() { for (int i = 2; i < MAXN; ++i) if (!mpr[i]) for (int j = i; j < MAXN; j += i) mpr[j] = i; } int calc(int n) { int ret = 0; while (n > 1) n /= mpr[n], ++ret; return ret; } int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } int main() { freopen("EQUAL.INP","r",stdin); freopen("EQUAL.OUT","w",stdout); sieve(); int q; cin >> q; while (q--) { int res = 0, a, b; cin >> a >> b; int uc = gcd(a, b); a /= uc, b /= uc; cout << max(calc(a), calc(b)) << '\n'; } return 0; }
Comments