fork download 
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("avx,avx2,fma")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define MOD 1000000007
  9. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  10. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define ii pair<ll,ll>
  13. #define iii pair<ll,pair<ll,int>>
  14. //const int MOD = 998244353;
  15. const int MAXN = 2e6 + 7;
  16. int dd[MAXN],prime[MAXN];
  17. vector<int> p;
  18. void sieve(){
  19.     prime[1] = 1;
  20.     FOR(i,1,(int)sqrt(MAXN))if (!prime[i]){
  21.         prime[i] = i;
  22.         for (int j = i * i;j <= MAXN;j+=i)prime[j] = i;
  23.     }
  24. }
  25. ll calc(ll n){
  26.     ll ans = 0;
  27.     for (auto d : p)ans = ans + (dd[d] & 1 ? 1 : -1) * n / d;
  28.     return ans;
  29. }
  30. int main(){
  31.     ios_base::sync_with_stdio(false);
  32.     cin.tie(0); cout.tie(0);
  33.     //freopen("CONNECT.inp","r",stdin);
  34.     //freopen("CONNECT.out","w",stdout);
  35.     sieve();
  36.     int tt;cin >> tt;
  37.     while(tt--){
  38.         ll a,b,c;cin >> a >> b >> c;
  39.         p.clear();vector<int> v;
  40.         FOR(i,1,(int)sqrt(b))if (b % i == 0){
  41.             p.push_back(i);
  42.             if (b / i != i)v.push_back(b / i);
  43.         }
  44.         break;
  45.         for (auto d : p){
  46.             int n = d;
  47.             dd[d] = 1;
  48.             while(n > 1){
  49.                 if (prime[n] == 1){
  50.                     cout << 1 << ' ';
  51.                     break;
  52.                 }
  53.                 dd[d]++;
  54.                 n = n / prime[n];
  55.             }
  56.         }
  57.         break;
  58.         c = c + calc(a);
  59.         ll l = 1,r = 1ll * b * c + a + 1,ans;
  60.         while (l <= r){
  61.             ll mid = (l + r) / 2;
  62.             if (calc(mid) >= c){
  63.                 ans = mid;
  64.                 r = mid - 1;
  65.             }else l = mid + 1;
  66.         }
  67.         cout << ans << '\n';
  68.     }
  69.     return 0^0;
  70. }
  71.  
  72.  
Success #stdin #stdout 0.02s 13160KB
comments (?)
stdin 
3
3 4 5
4 5 6
5 6 7
stdout 
Standard output is empty
https://ideone.com/6Qur1s
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!