QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#361910#8508. DiviDueloucup-team133#AC ✓3ms3884kbC++234.5kb2024-03-23 13:36:022024-03-23 13:36:03

Judging History

This is the latest submission verdict.

  • [2024-03-23 13:36:03]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 3884kb
  • [2024-03-23 13:36:02]
  • Submitted

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

namespace elementary_math {

template <typename T> std::vector<T> divisor(T n) {
    std::vector<T> res;
    for (T i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i * i != n) res.emplace_back(n / i);
        }
    }
    return res;
}

template <typename T> std::vector<std::pair<T, int>> prime_factor(T n) {
    std::vector<std::pair<T, int>> res;
    for (T p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            res.emplace_back(p, 0);
            while (n % p == 0) {
                res.back().second++;
                n /= p;
            }
        }
    }
    if (n > 1) res.emplace_back(n, 1);
    return res;
}

std::vector<int> osa_k(int n) {
    std::vector<int> min_factor(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (min_factor[i]) continue;
        for (int j = i; j <= n; j += i) {
            if (!min_factor[j]) {
                min_factor[j] = i;
            }
        }
    }
    return min_factor;
}

std::vector<int> prime_factor(const std::vector<int>& min_factor, int n) {
    std::vector<int> res;
    while (n > 1) {
        res.emplace_back(min_factor[n]);
        n /= min_factor[n];
    }
    return res;
}

long long modpow(long long x, long long n, long long mod) {
    assert(0 <= n && 1 <= mod && mod < (1LL << 31));
    if (mod == 1) return 0;
    x %= mod;
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

long long extgcd(long long a, long long b, long long& x, long long& y) {
    long long d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else
        x = 1, y = 0;
    return d;
}

long long inv_mod(long long a, long long mod) {
    assert(1 <= mod);
    long long x, y;
    if (extgcd(a, mod, x, y) != 1) return -1;
    return (mod + x % mod) % mod;
}

template <typename T> T euler_phi(T n) {
    auto pf = prime_factor(n);
    T res = n;
    for (const auto& p : pf) {
        res /= p.first;
        res *= p.first - 1;
    }
    return res;
}

std::vector<int> euler_phi_table(int n) {
    std::vector<int> res(n + 1, 0);
    iota(res.begin(), res.end(), 0);
    for (int i = 2; i <= n; i++) {
        if (res[i] != i) continue;
        for (int j = i; j <= n; j += i) res[j] = res[j] / i * (i - 1);
    }
    return res;
}

// minimum i > 0 s.t. x^i \equiv 1 \pmod{m}
template <typename T> T order(T x, T m) {
    T n = euler_phi(m);
    auto cand = divisor(n);
    sort(cand.begin(), cand.end());
    for (auto& i : cand) {
        if (modpow(x, i, m) == 1) {
            return i;
        }
    }
    return -1;
}

template <typename T> std::vector<std::tuple<T, T, T>> quotient_ranges(T n) {
    std::vector<std::tuple<T, T, T>> res;
    T m = 1;
    for (; m * m <= n; m++) res.emplace_back(m, m, n / m);
    for (; m >= 1; m--) {
        T l = n / (m + 1) + 1, r = n / m;
        if (l <= r and std::get<1>(res.back()) < l) res.emplace_back(l, r, n / l);
    }
    return res;
}

}  // namespace elementary_math

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N;
    cin >> N;

    auto ps = elementary_math::prime_factor(N);
    int n = ps.size();
    if (n > 2 or n == 0) {
        cout << "N\n";
        return 0;
    }
    if (n == 1) {
        cout << (ps[0].second & 1 ? "Y" : "N") << "\n";
    } else {
        cout << (ps[0].second == 1 and ps[1].second == 1 ? "Y" : "N") << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3844kb

input:

10

output:

Y

result:

ok "Y"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

9

output:

N

result:

ok "N"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

1

output:

N

result:

ok "N"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

549755813888

output:

Y

result:

ok "Y"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

274877906944

output:

N

result:

ok "N"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

847288609443

output:

Y

result:

ok "Y"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

282429536481

output:

N

result:

ok "N"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

137858491849

output:

N

result:

ok "N"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

10604499373

output:

Y

result:

ok "Y"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

506623120463

output:

Y

result:

ok "Y"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

10779215329

output:

N

result:

ok "N"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

41910794561

output:

Y

result:

ok "Y"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

64574155417

output:

Y

result:

ok "Y"

Test #14:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

75644818241

output:

Y

result:

ok "Y"

Test #15:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

124029899611

output:

Y

result:

ok "Y"

Test #16:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

134306640043

output:

Y

result:

ok "Y"

Test #17:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

146462570411

output:

Y

result:

ok "Y"

Test #18:

score: 0
Accepted
time: 2ms
memory: 3812kb

input:

222287988673

output:

Y

result:

ok "Y"

Test #19:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

263345887171

output:

Y

result:

ok "Y"

Test #20:

score: 0
Accepted
time: 3ms
memory: 3544kb

input:

717451682557

output:

Y

result:

ok "Y"

Test #21:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

825365364157

output:

Y

result:

ok "Y"

Test #22:

score: 0
Accepted
time: 3ms
memory: 3872kb

input:

870298842859

output:

Y

result:

ok "Y"

Test #23:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

887915259331

output:

Y

result:

ok "Y"

Test #24:

score: 0
Accepted
time: 3ms
memory: 3576kb

input:

967108197509

output:

Y

result:

ok "Y"

Test #25:

score: 0
Accepted
time: 3ms
memory: 3640kb

input:

990661375799

output:

Y

result:

ok "Y"

Test #26:

score: 0
Accepted
time: 3ms
memory: 3804kb

input:

999999999989

output:

Y

result:

ok "Y"

Test #27:

score: 0
Accepted
time: 3ms
memory: 3580kb

input:

999962000357

output:

Y

result:

ok "Y"

Test #28:

score: 0
Accepted
time: 3ms
memory: 3532kb

input:

999474022513

output:

Y

result:

ok "Y"

Test #29:

score: 0
Accepted
time: 3ms
memory: 3680kb

input:

999052035451

output:

Y

result:

ok "Y"

Test #30:

score: 0
Accepted
time: 3ms
memory: 3588kb

input:

999470040641

output:

Y

result:

ok "Y"

Test #31:

score: 0
Accepted
time: 3ms
memory: 3576kb

input:

998712349711

output:

Y

result:

ok "Y"

Test #32:

score: 0
Accepted
time: 3ms
memory: 3644kb

input:

998768376647

output:

Y

result:

ok "Y"

Test #33:

score: 0
Accepted
time: 3ms
memory: 3680kb

input:

998884311283

output:

Y

result:

ok "Y"

Test #34:

score: 0
Accepted
time: 3ms
memory: 3808kb

input:

998794254709

output:

Y

result:

ok "Y"

Test #35:

score: 0
Accepted
time: 3ms
memory: 3844kb

input:

998830303021

output:

Y

result:

ok "Y"

Test #36:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

999638023157

output:

Y

result:

ok "Y"

Test #37:

score: 0
Accepted
time: 3ms
memory: 3528kb

input:

998978227997

output:

Y

result:

ok "Y"

Test #38:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

999108034891

output:

Y

result:

ok "Y"

Test #39:

score: 0
Accepted
time: 3ms
memory: 3880kb

input:

998922289621

output:

Y

result:

ok "Y"

Test #40:

score: 0
Accepted
time: 3ms
memory: 3644kb

input:

999172169371

output:

Y

result:

ok "Y"

Test #41:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

999218015981

output:

Y

result:

ok "Y"

Test #42:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

981700934653

output:

N

result:

ok "N"

Test #43:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

942804229201

output:

N

result:

ok "N"

Test #44:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

822635014967

output:

N

result:

ok "N"

Test #45:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

954312321917

output:

N

result:

ok "N"

Test #46:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

965687001953

output:

N

result:

ok "N"

Test #47:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

907803030577

output:

N

result:

ok "N"

Test #48:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

993916557163

output:

N

result:

ok "N"

Test #49:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

844029771131

output:

N

result:

ok "N"

Test #50:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

862969367597

output:

N

result:

ok "N"

Test #51:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

768706748179

output:

N

result:

ok "N"

Test #52:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

744412255649

output:

N

result:

ok "N"

Test #53:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

877760921347

output:

N

result:

ok "N"

Test #54:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

779321766481

output:

N

result:

ok "N"

Test #55:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

786676948027

output:

N

result:

ok "N"

Test #56:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

775686765629

output:

N

result:

ok "N"

Test #57:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

971230541

output:

N

result:

ok "N"

Test #58:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

2385673

output:

N

result:

ok "N"

Test #59:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

52468711

output:

N

result:

ok "N"

Test #60:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

20358337

output:

N

result:

ok "N"

Test #61:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

9186689

output:

N

result:

ok "N"

Test #62:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

106251

output:

N

result:

ok "N"

Test #63:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

2859061

output:

N

result:

ok "N"

Test #64:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

51455519

output:

N

result:

ok "N"

Test #65:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

68063771

output:

N

result:

ok "N"

Test #66:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

44480353

output:

N

result:

ok "N"

Test #67:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

445130407

output:

N

result:

ok "N"

Test #68:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

54924301

output:

N

result:

ok "N"

Test #69:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

251377811

output:

N

result:

ok "N"

Test #70:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

11583287

output:

N

result:

ok "N"

Test #71:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

164689969

output:

N

result:

ok "N"

Test #72:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

220388553874

output:

N

result:

ok "N"

Test #73:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

337917710393

output:

N

result:

ok "N"

Test #74:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

484109724475

output:

N

result:

ok "N"

Test #75:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

494253368469

output:

N

result:

ok "N"

Test #76:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

790636814905

output:

N

result:

ok "N"

Test #77:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

593466711078

output:

N

result:

ok "N"

Test #78:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

701257784810

output:

N

result:

ok "N"

Test #79:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

821468484315

output:

N

result:

ok "N"

Test #80:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

321582188478

output:

N

result:

ok "N"

Test #81:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

623403649385

output:

N

result:

ok "N"

Test #82:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

172509105650

output:

N

result:

ok "N"

Test #83:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

579709456395

output:

N

result:

ok "N"

Test #84:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

703541153630

output:

N

result:

ok "N"

Test #85:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

371717528455

output:

N

result:

ok "N"

Test #86:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

925436174850

output:

N

result:

ok "N"

Test #87:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

441602590298

output:

N

result:

ok "N"

Test #88:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

663345923451

output:

N

result:

ok "N"

Test #89:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

662812798173

output:

N

result:

ok "N"

Test #90:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

662615302233

output:

N

result:

ok "N"

Test #91:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

663436223391

output:

N

result:

ok "N"

Test #92:

score: 0
Accepted
time: 2ms
memory: 3532kb

input:

662248872237

output:

N

result:

ok "N"

Test #93:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

662516706867

output:

N

result:

ok "N"

Test #94:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

864077614394

output:

N

result:

ok "N"

Test #95:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

977802486226

output:

N

result:

ok "N"

Test #96:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

647426786602

output:

N

result:

ok "N"

Test #97:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

901679277046

output:

N

result:

ok "N"

Test #98:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

642523777682

output:

N

result:

ok "N"

Test #99:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

871506220334

output:

N

result:

ok "N"

Test #100:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

950098378534

output:

N

result:

ok "N"

Test #101:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

660409283986

output:

N

result:

ok "N"

Test #102:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

819550638458

output:

N

result:

ok "N"

Test #103:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

846693913942

output:

N

result:

ok "N"

Test #104:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

630683996246

output:

N

result:

ok "N"

Test #105:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

698348891974

output:

N

result:

ok "N"

Test #106:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

794129725534

output:

N

result:

ok "N"

Test #107:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

731864249762

output:

N

result:

ok "N"

Test #108:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

758461160882

output:

N

result:

ok "N"

Test #109:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

200560490130

output:

N

result:

ok "N"

Test #110:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

132843110400

output:

N

result:

ok "N"

Test #111:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

700131600000

output:

N

result:

ok "N"

Test #112:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

755827200000

output:

N

result:

ok "N"

Test #113:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

3368254499

output:

Y

result:

ok "Y"

Test #114:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

338171833063

output:

Y

result:

ok "Y"

Test #115:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

182187833309

output:

Y

result:

ok "Y"

Test #116:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

207790265467

output:

Y

result:

ok "Y"

Test #117:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

101847563

output:

Y

result:

ok "Y"

Test #118:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

32187778741

output:

Y

result:

ok "Y"

Test #119:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

50284268371

output:

Y

result:

ok "Y"

Test #120:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

237176659

output:

Y

result:

ok "Y"

Test #121:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

6570725617

output:

Y

result:

ok "Y"

Test #122:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

11194326053

output:

Y

result:

ok "Y"

Test #123:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

288804781

output:

Y

result:

ok "Y"

Test #124:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

683099533943

output:

Y

result:

ok "Y"

Test #125:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

77909194511

output:

Y

result:

ok "Y"

Test #126:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

633839779

output:

Y

result:

ok "Y"

Test #127:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

49714249733

output:

Y

result:

ok "Y"

Test #128:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

60781478521

output:

N

result:

ok "N"

Test #129:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

6340459129

output:

N

result:

ok "N"

Test #130:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

582784140409

output:

N

result:

ok "N"

Test #131:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

106704795649

output:

N

result:

ok "N"

Test #132:

score: 0
Accepted
time: 2ms
memory: 3880kb

input:

364295537761

output:

N

result:

ok "N"

Test #133:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

48194738089

output:

N

result:

ok "N"

Test #134:

score: 0
Accepted
time: 3ms
memory: 3840kb

input:

534067178401

output:

N

result:

ok "N"

Test #135:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

266490315529

output:

N

result:

ok "N"

Test #136:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

41293897681

output:

N

result:

ok "N"

Test #137:

score: 0
Accepted
time: 2ms
memory: 3880kb

input:

405579196201

output:

N

result:

ok "N"

Test #138:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

7659225289

output:

N

result:

ok "N"

Test #139:

score: 0
Accepted
time: 3ms
memory: 3580kb

input:

650447089009

output:

N

result:

ok "N"

Test #140:

score: 0
Accepted
time: 3ms
memory: 3528kb

input:

856407728929

output:

N

result:

ok "N"

Test #141:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

536053872649

output:

N

result:

ok "N"

Test #142:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

48390760441

output:

N

result:

ok "N"

Extra Test:

score: 0
Extra Test Passed