結果
問題 | No.2526 Kth Not-divisible Number |
ユーザー |
![]() |
提出日時 | 2023-11-03 21:32:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 263 ms / 2,000 ms |
コード長 | 1,831 bytes |
コンパイル時間 | 1,007 ms |
コンパイル使用メモリ | 104,020 KB |
最終ジャッジ日時 | 2025-02-17 17:45:57 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 11 |
ソースコード
// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include <algorithm>#include <bitset>#include <cassert>#include <climits>#include <cmath>#include <complex>#include <deque>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <set>#include <string>#include <tuple>#include <vector>using namespace std;using ll = long long;using pii = pair<int, int>;using pll = pair<ll, ll>;#define TEST cerr << "TEST" << endl#define AMARI 998244353// #define AMARI 1000000007#define TIME_LIMIT 1980000#define el '\n'#define El '\n'long long ococo_gcd(long long a, long long b) {if(a < b) {swap(a,b);}if(b == 0 && a != 0)return a;long long ans = a;while(a % b) {long long kari = b;b = a % b;a = kari;}return min(a, b);}ll lcm(ll a,ll b){return (a * b) / ococo_gcd(a,b);}//[1,x]の中で、pまたはqで割り切れる数がa個以上かどうか lmはlcm(p,q)を入れるbool func(ll x,ll p,ll q,ll lm,ll a){ll cnt1 = x - x / p,cnt2 = x - x / q,cnt3 = x - x / lm;if(cnt1 + cnt2 - cnt3 >= a)return true;else return false;}#define MULTI_TEST_CASE truevoid solve(void) {ll a,b,k;cin >> a >> b >> k;ll lm = lcm(a,b);ll l = 0,r = 4LL * k;while(r - l >= 2){ll c = (r + l) / 2;if(func(c,a,b,lm,k))r = c;else l = c;}for(ll i = l; i <= r; i++){if(func(i,a,b,lm,k)){cout << i << el;return;}}assert(0);return;}void calc(void) {return;}signed main(void) {cin.tie(nullptr);ios::sync_with_stdio(false);calc();int t = 1;if(MULTI_TEST_CASE) cin >> t;while(t--) {solve();}return 0;}