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
?
?
?
?`