結果
問題 | No.1936 Rational Approximation |
ユーザー |
![]() |
提出日時 | 2022-05-14 19:52:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 771 bytes |
コンパイル時間 | 1,610 ms |
コンパイル使用メモリ | 166,448 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 06:33:59 |
合計ジャッジ時間 | 2,392 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 14 |
ソースコード
/** * @FileName a.cpp * @Author kanpurin * @Created 2022.05.14 19:52:20 **/ #include "bits/stdc++.h" using namespace std; typedef long long ll; template<typename T> T extgcd(T a, T b, T &x, T &y) { if (b == 0) { x = 1; y = 0; return a; } T d = extgcd(b, a%b, y, x); y -= a / b * x; return d; } ll solveL(int p,int q) { int x,y; int g = extgcd(p,-q,x,y); if (g < 0) x = -x, y = -y; if (x < 0 || y < 0) x += q, y += p; return x+y; } ll solveR(int p,int q) { int x,y; int g = extgcd(-p,q,x,y); if (g < 0) x = -x, y = -y; if (x < 0 || y < 0) x += q, y += p; return x+y; } int main() { int p,q;cin >> p >> q; cout << solveL(p,q) + solveR(p,q) << endl; return 0; }