QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#43069 | #2965. RSA Mistake | sinbad# | AC ✓ | 3ms | 3748kb | C++ | 7.2kb | 2022-08-06 10:34:35 | 2022-08-06 10:34:36 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'