Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
34929188 Practice:
hamayanhamayan
920G - 6 GNU C++14 Accepted 2558 ms 1996 KB 2018-02-04 21:48:10 2018-02-04 21:48:10
 
 
→ Source
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
map<int, int> enumpr(int n) {
    map<int, int> V;
    for (int i = 2; 1LL * i*i <= n; i++) while (n%i == 0) V[i]++, n /= i;
    if (n>1) V[n]++;
    return V;
}
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/







int X, P, K;
vector<int> primes;
//---------------------------------------------------------------------------------------------------
ll count(int x) {
    int n = primes.size();
    ll res = 0;
    rep(msk, 0, 1 << n) {
        int c = 0, y = 1;
        rep(i, 0, n) if (msk & (1 << i)) c++, y *= primes[i];
        if (c % 2 == 0) res += x / y;
        else res -= x / y;
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
int check(int x) {
    ll cnt = count(x) - count(X);
    return K <= cnt;
}
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> X >> P >> K;

    auto ep = enumpr(P);
    primes.clear();
    fore(p, ep) primes.push_back(p.first);

    int ng = X, ok = inf;
    while (ng + 1 != ok) {
        int x = (ok + ng) / 2;
        if (check(x)) ok = x;
        else ng = x;
    }

    printf("%d\n", ok);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details