fork download
copy 
  1. /**
  2.     * Makacha
  3. **/
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. typedef long long ll;
  7. ll x, y, res, n, a[1000111];
  8. inline void Fact(ll x) {
  9.     int y = sqrt(x);
  10.     for (int i = 2; i <= y; i++) {
  11.         if (x % i == 0) {
  12.             while (x % i == 0)
  13.                 x /= i;
  14.             a[++n] = i;
  15.         }
  16.     }
  17.     if (x > 1)
  18.         a[++n] = x;
  19. }
  20. inline bool Check(ll u, ll v) {
  21.     for (int i = 1; i <= n; i++)
  22.         if (x % a[i] == 0 && u / a[i] != v / a[i])
  23.             return false;
  24.     return true;
  25. }
  26. int main() {
  27.     cin >> x >> y;
  28.     Fact(x);
  29.     while (y) {
  30.         for (int i = 1; i <= n; i++)
  31.             if (x % a[i] == 0 && a[i] <= y)
  32.                 goto line0;
  33.         res += y;
  34.         break;
  35.         line0:;
  36.         ll l = 1, r = y;
  37.         while (l <= r) {
  38.             ll mid = l + r >> 1;
  39.             if (Check(mid, y))
  40.                 r = mid - 1;
  41.             else
  42.                 l = mid + 1;
  43.         }
  44.         res += y - l + 1;
  45.         y = l / __gcd(x, l) - 1;
  46.         x /= __gcd(x, l);
  47.     }
  48.     cout << res;
  49. }
  50.  
Success #stdin #stdout 0.01s 5568KB
comments (?)
stdin
copy 
4 9
stdout
copy 
3
https://ideone.com/dZwAY5
language:
C++14 (gcc 8.3)
created:
1 year 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!