結果
問題 | No.2767 Add to Divide |
ユーザー |
|
提出日時 | 2024-05-31 21:48:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 1,653 bytes |
コンパイル時間 | 3,564 ms |
コンパイル使用メモリ | 254,124 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 23:08:00 |
合計ジャッジ時間 | 4,472 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;/*/#include <atcoder/all>using namespace atcoder;#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")#pragma GCC target("avx,avx2,fma")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")//*/#define rep(i,n) for(int i=0;i<n;i++)#define Rep(i,a,b) for(int i=a;i<b;i++)#define ALL(x) (x).begin(),(x).end()#define dbgv(x); for(auto now : x) cout << now << " "; cout << endl;//using P = pair<int,int>;using ll = long long;using ull = unsigned long long;//*/template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef vector<ll> vll;typedef vector<int> vint;random_device rnd;mt19937 rng(rnd());vector<long long> divisor(long long n) {vector<long long> ret;for (long long i = 1; i*i <= n; i++) {if (n % i == 0) {ret.push_back(i);if(n/i != i) ret.push_back(n/i);}}sort(ret.begin(),ret.end());return ret;}void solve(){ll a,b; cin >> a >> b;if(b%a==0){cout << 0 << endl;return;}auto v = divisor(b-a);const ll INF = 1e18;ll ans = INF;rep(i,v.size()){if(a*(v[i]+1) > b) break;else chmin(ans,(b-(v[i]+1)*a)/(v[i]));}if(ans == INF) cout << -1 << endl;else cout << ans << endl;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1; cin >> t;rep(testcases,t) solve();}