結果
問題 | No.2882 Comeback |
ユーザー |
![]() |
提出日時 | 2024-08-04 19:18:17 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 2,000 ms |
コード長 | 1,712 bytes |
コンパイル時間 | 2,810 ms |
コンパイル使用メモリ | 252,860 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-12 11:13:06 |
合計ジャッジ時間 | 4,998 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++)#define ll long longvoid solve() {int A, B; cin >> A >> B;vector<int> ABdiv;for (int d = 1; d * d <= A; d++) {ABdiv.push_back(d);ABdiv.push_back(A/d);}for (int d = 1; d * d <= B; d++) {ABdiv.push_back(d);ABdiv.push_back(B/d);}//降順にソートsort(ABdiv.begin(), ABdiv.end(), greater<int>());//重複削除ABdiv.erase(unique(ABdiv.begin(), ABdiv.end()), ABdiv.end());int N = (int)ABdiv.size();ABdiv.push_back(0); //番兵int ans = 0;for (int i = 0; i < N; i++) {//初項int fa = A%ABdiv[i], fb = B%ABdiv[i];//公差int da = A/ABdiv[i], db = B/ABdiv[i];//打ち切り限界int len = ABdiv[i]-ABdiv[i+1];//一次式の不等式を解く//x項目について、//fa + da*x >= fb + db * x//(da-db)x >= fb-fa//x <= (fb-fa)/(da-db) (B > A より、da >= db)//x <= (fa-fb)/(db-da) (db-daで割ることによって、正整数の除算にする)//ゼロ除算を防止if (da == db) {if (fa >= fb) ans += len; //逆転しないcontinue;}//答えが負になるので、初めから負けている。何も足さないif (fa-fb < 0) continue;int x = (fa-fb)/(db-da);//打ち切りif (x >= len) x = len-1;//0-indexedだったので、+1して数えるans += x+1;}cout << ans << endl;}int main() {int T; cin >> T;rep(_, 0, T) {solve();}}