QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#43069#2965. RSA Mistakesinbad#AC ✓3ms3748kbC++7.2kb2022-08-06 10:34:352022-08-06 10:34:36

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-06 10:34:36]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3748kb
  • [2022-08-06 10:34:35]
  • 提交

answer

#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
  return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}

using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
int lg2(int64 x) { return sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;


struct Mint {
  int64 n;
  static int64 mod, inv, r2;
  Mint() : n(0) { }
  Mint(const int64 &x) : n(init(x)) { }
  static int64 init(const int64 &w) { return reduce(__uint128_t(w) * r2); }
  static void set_mod(const int64 &m) {
    mod = inv = m;
    for (int i = 0; i < 5; ++i) inv *= 2 - inv * m;
    r2 = -__uint128_t(m) % m;
  }
  static int64 reduce(const __uint128_t &x) {
    int64 y = int64(x >> 64) - int64((__uint128_t(int64(x) * inv) * mod) >> 64);
    return int64_t(y) < 0 ? y + mod : y;
  }
  Mint& operator +=(const Mint &x) { n += x.n - mod; if (int64_t(n) < 0) n += mod; return *this; }
  Mint& operator +(const Mint &x) const { return Mint(*this) += x; }
  Mint& operator *=(const Mint &x) { n = reduce(__uint128_t(n) * x.n); return *this; }
  Mint& operator *(const Mint &x) const { return Mint(*this) *= x; }
  int64 val() const { return reduce(n); }
};

int64 Mint::mod, Mint::inv, Mint::r2;

bool suspect(const int64 &a, const int64 &s, int64 d, const int64 &n) {
  if (Mint::mod != n)  Mint::set_mod(n);
  Mint x(1), xx(a), one(x), minusone(n - 1);
  while (d > 0) {
    if (d & 1) x *= xx;
    xx *= xx;
    d >>= 1;
  }
  if (x.n == one.n)  return true;
  for (unsigned int r = 0; r < s; ++r) {
    if (x.n == minusone.n) return true;
    x *= x;
  }
  return false;
}

bool is_prime(const int64 &n) {
  if (n <= 1 || (n > 2 && (~n & 1))) return false;
  int64 d = n - 1, s = 0;
  while (~d & 1) ++s, d >>= 1;
  static const int64 a_big[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  static const int64 a_smol[] = {2, 7, 61};
  if (n <= 4759123141LL) {
    for (auto &&p : a_smol) {
      if (p >= n)  break;
      if (!suspect(p, s, d, n))  return false;
    }
  } else {
    for (auto &&p : a_big) {
      if (p >= n)  break;
      if (!suspect(p, s, d, n))  return false;
    }
  }
  return true;
}

int64 rho_pollard(const int64 &n) {
  if (~n & 1)  return 2u;
  static random_device rng;
  uniform_int_distribution<int64> rr(1, n - 1);
  if (Mint::mod != n)  Mint::set_mod(n);
  for (;;) {
    int64 c_ = rr(rng), g = 1, r = 1, m = 500;
    Mint y(rr(rng)), xx(0), c(c_), ys(0), q(1);
    while (g == 1) {
      xx.n = y.n;
      for (unsigned int i = 1; i <= r; ++i)  y *= y, y += c;
      int64 k = 0; g = 1;
      while (k < r && g == 1) {
        for (unsigned int i = 1; i <= (m > (r - k) ? (r - k) : m); ++i) {
          ys.n = y.n;
          y *= y; y += c;
          int64 xxx = xx.val(), yyy = y.val();
          q *= Mint(xxx > yyy ? xxx - yyy : yyy - xxx);
        }
        g = gcd(q.val(), n);
        k += m;
      }
      r *= 2;
    }
    if (g == n) g = 1;
    while (g == 1) {
      ys *= ys; ys += c;
      int64 xxx = xx.val(), yyy = ys.val();
      g = gcd(xxx > yyy ? xxx - yyy : yyy - xxx, n);
    }
    if (g != n && is_prime(g)) return g;
  }
}

vector<int64> factor(int64 n) {
  if (n < 2) return {};
  if (is_prime(n)) return {n};
  int64 d = rho_pollard(n);
  vector<int64> L = factor(d), R = factor(n / d);
  L.insert(L.end(), R.begin(), R.end());
  return L;
}

int main() {
  int64 p, q;
  cin >> p >> q;
  if (is_prime(p) && is_prime(q) && p != q) {
    cout << "full credit" << '\n';
  } else {
    vector<int64> a;
    for (auto& x : factor(p)) a.push_back(x);
    for (auto& x : factor(q)) a.push_back(x);
    sort(a.begin(), a.end());
    bool ok = 1;
    for (int i = 0, j; i < SZ(a); i = j) {
      for (j = i + 1; j < SZ(a) && a[j] == a[i]; ++j);
      if (j - i > 1) ok =0;
    }
    cout << (ok ? "partial credit" : "no credit") << '\n';
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 3700kb

input:

13 23

output:

full credit

result:

ok single line: 'full credit'

Test #2:

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

input:

35 6

output:

partial credit

result:

ok single line: 'partial credit'

Test #3:

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

input:

4 5

output:

no credit

result:

ok single line: 'no credit'

Test #4:

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

input:

17 17

output:

no credit

result:

ok single line: 'no credit'

Test #5:

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

input:

15 21

output:

no credit

result:

ok single line: 'no credit'

Test #6:

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

input:

545528636581 876571629707

output:

no credit

result:

ok single line: 'no credit'

Test #7:

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

input:

431348146441 3

output:

no credit

result:

ok single line: 'no credit'

Test #8:

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

input:

584803025179 200560490130

output:

partial credit

result:

ok single line: 'partial credit'

Test #9:

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

input:

725769156026 520807975733

output:

partial credit

result:

ok single line: 'partial credit'

Test #10:

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

input:

94785999423 831843785340

output:

no credit

result:

ok single line: 'no credit'

Test #11:

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

input:

962631984045 923583932904

output:

no credit

result:

ok single line: 'no credit'

Test #12:

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

input:

983892174682 596267564620

output:

no credit

result:

ok single line: 'no credit'

Test #13:

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

input:

988586693791 523281177667

output:

full credit

result:

ok single line: 'full credit'

Test #14:

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

input:

768483880537 958632922673

output:

full credit

result:

ok single line: 'full credit'

Test #15:

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

input:

695320496641 992131878511

output:

full credit

result:

ok single line: 'full credit'

Test #16:

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

input:

619864432127 575182057589

output:

full credit

result:

ok single line: 'full credit'

Test #17:

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

input:

574224928327 554785761851

output:

full credit

result:

ok single line: 'full credit'

Test #18:

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

input:

2 2

output:

no credit

result:

ok single line: 'no credit'

Test #19:

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

input:

999999999989 999999999961

output:

full credit

result:

ok single line: 'full credit'

Test #20:

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

input:

999999999989 999999999989

output:

no credit

result:

ok single line: 'no credit'

Test #21:

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

input:

2 999999999989

output:

full credit

result:

ok single line: 'full credit'

Test #22:

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

input:

999999999989 2

output:

full credit

result:

ok single line: 'full credit'

Test #23:

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

input:

799337241719 790574179457

output:

no credit

result:

ok single line: 'no credit'

Test #24:

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

input:

999962000357 999944000663

output:

no credit

result:

ok single line: 'no credit'

Test #25:

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

input:

2 4

output:

no credit

result:

ok single line: 'no credit'

Test #26:

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

input:

4 2

output:

no credit

result:

ok single line: 'no credit'

Test #27:

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

input:

21 15

output:

no credit

result:

ok single line: 'no credit'

Test #28:

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

input:

5 4

output:

no credit

result:

ok single line: 'no credit'

Test #29:

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

input:

125 7

output:

no credit

result:

ok single line: 'no credit'

Test #30:

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

input:

999999999969 999999999929

output:

partial credit

result:

ok single line: 'partial credit'

Test #31:

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

input:

428571428541 999999999929

output:

no credit

result:

ok single line: 'no credit'

Test #32:

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

input:

949999999373 714080161721

output:

partial credit

result:

ok single line: 'partial credit'

Test #33:

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

input:

757523014201 616759792799

output:

partial credit

result:

ok single line: 'partial credit'

Test #34:

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

input:

945410323183 793541296879

output:

partial credit

result:

ok single line: 'partial credit'

Test #35:

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

input:

668134918943 250092815711

output:

partial credit

result:

ok single line: 'partial credit'

Test #36:

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

input:

593159028797 378923570503

output:

partial credit

result:

ok single line: 'partial credit'

Test #37:

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

input:

673663445657 685555556761

output:

partial credit

result:

ok single line: 'partial credit'

Test #38:

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

input:

615590502287 730111591619

output:

partial credit

result:

ok single line: 'partial credit'

Test #39:

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

input:

737474530367 339061475591

output:

partial credit

result:

ok single line: 'partial credit'

Test #40:

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

input:

547304948893 825051092141

output:

partial credit

result:

ok single line: 'partial credit'

Test #41:

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

input:

888259990703 349508614421

output:

partial credit

result:

ok single line: 'partial credit'

Test #42:

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

input:

394206923881 679230181703

output:

no credit

result:

ok single line: 'no credit'

Test #43:

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

input:

199036422587 813176211779

output:

no credit

result:

ok single line: 'no credit'

Test #44:

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

input:

385196736923 358517468791

output:

no credit

result:

ok single line: 'no credit'

Test #45:

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

input:

540003052801 543341442493

output:

no credit

result:

ok single line: 'no credit'

Test #46:

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

input:

529883073493 557936045561

output:

no credit

result:

ok single line: 'no credit'

Test #47:

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

input:

519207113731 326410289771

output:

no credit

result:

ok single line: 'no credit'

Test #48:

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

input:

530779897367 729543471779

output:

no credit

result:

ok single line: 'no credit'

Test #49:

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

input:

623202833611 876138576449

output:

no credit

result:

ok single line: 'no credit'

Test #50:

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

input:

741753647069 741753647069

output:

no credit

result:

ok single line: 'no credit'

Test #51:

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

input:

548039 445335943361

output:

no credit

result:

ok single line: 'no credit'

Test #52:

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

input:

644483448731 611801529223

output:

no credit

result:

ok single line: 'no credit'

Test #53:

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

input:

498556835561 412089307169

output:

no credit

result:

ok single line: 'no credit'

Test #54:

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

input:

602312422583 602312422583

output:

no credit

result:

ok single line: 'no credit'

Test #55:

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

input:

517277 424820460851

output:

no credit

result:

ok single line: 'no credit'