結果

問題 No.1224 I hate Sqrt Inequality
ユーザー masayoshi361masayoshi361
提出日時 2020-09-11 21:55:34
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,554 bytes
コンパイル時間 2,169 ms
コンパイル使用メモリ 187,840 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-06-08 09:46:55
合計ジャッジ時間 5,431 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,624 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:213:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  213 |     for (auto [p, c] : bpf) {
      |               ^

ソースコード

diff # 

/* #region header */
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
// using namespace atcoder;
#ifdef LOCAL
#include "cxx-prettyprint-master/prettyprint.hpp"
void debug() { cout << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
    cout << " " << H;
    debug(T...);
}
#else
#define debug(...) 42
#endif
// types
using ll = long long;
using ull = unsigned long long;
using ld = long double;
typedef pair<ll, ll> Pl;
typedef pair<int, int> Pi;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vc;
template <typename T>
using mat = vector<vector<T>>;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef vector<vector<char>> vvc;

// abreviations
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep_(i, a_, b_, a, b, ...) for (ll i = (a), max_i = (b); i < max_i; i++)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define rrep_(i, a_, b_, a, b, ...) \
    for (ll i = (b - 1), min_i = (a); i >= min_i; i--)
#define rrep(i, ...) rrep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define SZ(x) ((ll)(x).size())
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define mp make_pair
#define print(x) cout << x << endl
#define vprint(x)                         \
    rep(i, x.size()) cout << x[i] << ' '; \
    cout << endl
#define vsum(x) accumulate(all(x), 0LL)
#define vmax(a) *max_element(all(a))
#define vmin(a) *min_element(all(a))
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
// functions
// gcd(0, x) fails.
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
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;
}
template <typename T>
T mypow(T x, ll n) {
    T ret = 1;
    while (n > 0) {
        if (n & 1) (ret *= x);
        (x *= x);
        n >>= 1;
    }
    return ret;
}
ll modpow(ll x, ll n, const ll mod) {
    ll ret = 1;
    while (n > 0) {
        if (n & 1) (ret *= x);
        (x *= x);
        n >>= 1;
        x %= mod;
        ret %= mod;
    }
    return ret;
}
uint64_t my_rand(void) {
    static uint64_t x = 88172645463325252ULL;
    x = x ^ (x << 13);
    x = x ^ (x >> 7);
    return x = x ^ (x << 17);
}
ll popcnt(ull x) { return __builtin_popcountll(x); }
// graph template
template <typename T>
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    bool operator<(const edge<T> &r) const { return cost < r.cost; }

    operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
struct Timer {
    clock_t start_time;
    void start() { start_time = clock(); }
    int lap() {
        // return x ms.
        return (clock() - start_time) * 1000 / CLOCKS_PER_SEC;
    }
};
/* #endregion*/
// constant
#define inf 1000000005
#define INF 4000000004000000000LL
#define mod 1000000007LL
#define endl '\n'
const long double eps = 0.000001;
const long double PI = 3.141592653589793;
// library
// MR is necessary
// In codeforces, delete __int128 in the second line.
// about O(N^1/4logN)
// codeforcesでは__int128が使えないので消すこと
// http :  // miller-rabin.appspot.com/
bool is_prime(ll n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    ll d = n - 1;
    while (d % 2 == 0) d /= 2;
    for (ll a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
        a %= n;
        if (a == 0) return true;
        ll t = d;
        ll y = modpow(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = __int128_t(y) * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
ll pollard_single(ll n) {
    auto f = [&](ll x) { return (__int128_t(x) * x + 1) % n; };
    // auto f = [&](ll x) { return (x * x + 1) % n; };
    if (is_prime(n)) return n;
    if (n % 2 == 0) return 2;
    ll st = 0;
    while (true) {
        st = my_rand() % n;
        ll x = st, y = f(x);
        while (true) {
            ll p = gcd((y - x + n), n);
            if (p == 0 || p == n) break;
            if (p != 1) return p;
            x = f(x);
            y = f(f(y));
        }
    }
}

vl pollard_rec(ll n) {
    if (n == 1) return {};
    ll x = pollard_single(n);
    if (x == n) return {x};
    vl a = pollard_rec(x);
    vl b = pollard_rec(n / x);
    a.insert(a.end(), b.begin(), b.end());
    return a;
}

map<ll, int> pollard(ll n) {
    map<ll, int> res;
    for (ll a : pollard_rec(n)) {
        res[a]++;
    }
    return res;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << setprecision(20);
    ll a, b;
    cin >> a >> b;
    auto bpf = pollard(b);
    auto apf = pollard(a);
    for (auto [p, c] : bpf) {
        if (p == 2 || p == 5) continue;
        if (apf[p] < c) {
            print("Yes");
            return 0;
        }
    }
    print("No");
}
0