제출 #872154

#제출 시각아이디문제언어결과실행 시간메모리
872154Onur_IlgazEuklid (COCI20_euklid)C++17
75 / 110
70 ms8576 KiB
#include <bits/stdc++.h> #define fast cin.tie(0)->sync_with_stdio(0); #define int long long #define inf ((int)1e18) #define N 66000005 using namespace std; void solve(){ int g, h; cin >> g >> h; bitset <N> dp; // if(dp[i]) then we can get R'(i, h) dp[1] = 1; for(int i = 1; i < N; i++) { if(!dp[i]) continue; if(i >= g) { int a = i, b = h; // a >= b garantili // cout << a << " " << b << "\n"; // cout << a << " " << b << "\n"; // b'yi g'nin katı yapacağız int need = (g - (a * b % g)) % g; b = a * b + need; // b artık g'nin katı // cout << a << " " << b << "\n"; swap(a, b); if(gcd(a, b) == g) { cout << a << " " << b << "\n\n"; return; } // a >= b garantili // a % g == 0 garantili b = a * b + ((a == g) ? 0 : g); cout << a << " " << b << "\n\n"; return; } for(int j = 0; j < h and i * h + j < N; j++) { dp[i * h + j] = 1; } } exit(1); } int32_t main(){ fast int t=1; cin>>t; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...