QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #790612 | #9299. ABC Conjecture | IllusionaryDominance# | AC ✓ | 64ms | 3832kb | C++20 | 3.2kb | 2024-11-28 14:01:40 | 2024-11-28 14:01:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u64 = unsigned long long;
namespace PR{
ll fac[1000000], cnt;
ll times(const ll &a, const ll &b, const ll &p) {
ll res = a * b - (ll)((long double)a / p * b + 0.5) * p;
return res < 0 ? res + p : res;
}
ll power(ll a, ll n, ll p) {
ll ans = 1;
a %= p;
while (n) {
if (n & 1) ans = times(ans, a, p);
a = times(a, a, p); n >>= 1;
}
return ans;
}
ll gcd(ll a, ll b) {
while (b) {
ll t = b;
b = a % b;
a = t;
}
return a;
}
bool check(const ll &x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i ++)
if (x % i == 0) return false;
return true;
}
bool miller_rabin(const ll &n) {
if (n < 100) return check(n);
if ((~ n & 1) || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 || n % 11 == 0 || n % 13 == 0 || n % 17 == 0 || n % 19 == 0 || n % 23 == 0 || n % 29 == 0) return false;
ll b = __builtin_ctzll(n - 1), x = (n - 1) >> b;
static int prime[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (int i = 0; i < 12; i ++) {
ll cur = power(prime[i], x, n), nxt;
for (int j = 1; j <= b && cur != 1; j ++) {
nxt = times(cur, cur, n);
if (nxt == 1 && cur != n - 1) {
return false;
}
cur = nxt;
}
if (cur != 1) {
return false;
}
}
return true;
}
ll add(const ll &a, const ll &b, const ll &p) {
u64 t = (u64)a + (u64)b;
t -= t < (u64)p ? 0 : p;
return t;
}
ll pollard_rho(const ll &n) {
ll c = (rand() << 15 | rand()) % n + 1, a1 = 0, a2;
a1 = add(times(a1, a1, n), c, n);
a2 = add(times(a1, a1, n), c, n);
while (a1 != a2) {
ll d = gcd(abs(a1 - a2), n);
if (d > 1) return d;
a1 = add(times(a1, a1, n), c, n);
a2 = add(times(a2, a2, n), c, n);
a2 = add(times(a2, a2, n), c, n);
}
return n;
}
void Do(ll n) {
if (n < 2) return ;
if (miller_rabin(n)) {
fac[++ cnt] = n;
return ;
}
ll s = sqrt(n);
if (s * s == n) {
Do(s); Do(s); return ;
}
s = pollard_rho(n);
while (s == 1 || s == n) s = pollard_rho(n);
Do(s); Do(n / s);
}
void solve(const ll &n) {
cnt = 0;
Do(n);
sort(fac + 1, fac + cnt + 1);
for (int i = 1; i < cnt; i ++) {
if (fac[i] == fac[i + 1]) {
cout << "yes\n";
return ;
}
}
cout << "no\n";
}
}
int main() {
srand(time(0));
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T --) {
ll n;
cin >> n;
PR::solve(n);
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
input:
3 4 18 30
output:
yes yes no
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
10 4 9 16 25 36 49 64 81 100 121
output:
yes yes yes yes yes yes yes yes yes yes
result:
ok 10 token(s): yes count is 10, no count is 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
10 2 3 5 7 11 13 17 19 23 29
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #4:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
10 6 15 35 77 80 91 143 75 101 99
output:
no no no no yes no no yes no yes
result:
ok 10 token(s): yes count is 3, no count is 7
Test #5:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
10 21271165 444231408 946974099 681758708 325191092 830145169 277367584 968476155 88497006 617591195
output:
no yes no yes yes no yes no no no
result:
ok 10 token(s): yes count is 4, no count is 6
Test #6:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
10 651358344 602420360 725327998 572443267 457046153 697433905 487646237 392673032 555857464 945521644
output:
yes yes no no no yes no yes yes yes
result:
ok 10 token(s): yes count is 6, no count is 4
Test #7:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
10 906018865 665033186 607653882 668356701 901353080 120481633 280656150 128862688 638961463 105591399
output:
no no yes no yes no yes yes no no
result:
ok 10 token(s): yes count is 4, no count is 6
Test #8:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
10 65445443 255551484 204787672 662332104 550012352 144811698 715122120 886333345 697093994 539928501
output:
no yes yes yes yes no yes no no yes
result:
ok 10 token(s): yes count is 6, no count is 4
Test #9:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
10 510848743 55465355 35314940 54709725 720341191 935607553 429552439 180835 749216312 923321369
output:
no no yes yes no no no no yes no
result:
ok 10 token(s): yes count is 3, no count is 7
Test #10:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
10 279828861859656668 779001228754992308 70180545249969207 602056351848582074 473743600510371898 884856863590340942 740404865423461786 254589470248048234 735418525187794654 19320655148995042
output:
yes yes no no no no no no no no
result:
ok 10 token(s): yes count is 2, no count is 8
Test #11:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
10 248100920920522972 709936117347778444 459577405205914080 514672244191507030 139155451158260882 213138886200801579 106206898325780866 131486604837012608 653930230455423892 139505921637452876
output:
yes yes yes no no yes no yes yes yes
result:
ok 10 token(s): yes count is 7, no count is 3
Test #12:
score: 0
Accepted
time: 3ms
memory: 3772kb
input:
10 774335048511012340 518965669654910057 456514773309199171 737863115914475813 697790523628491367 624324214072353799 576234677259441715 493566595158562629 518740639905632542 723857251834502731
output:
yes no no no no no no no no no
result:
ok 10 token(s): yes count is 1, no count is 9
Test #13:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
10 746268431380487389 524178555603669586 18759721267348523 518880659011666149 642159149181545555 399568396177004794 320017260154218612 644997645232057748 386637235567659791 458182658511422378
output:
no no no yes yes no yes yes no no
result:
ok 10 token(s): yes count is 4, no count is 6
Test #14:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
10 933397525551490748 576951839287405875 451486557641150171 767869673683059255 389890830833486456 378618686275821928 798952868585132570 993975228856643424 124136243135383452 883325348855313052
output:
yes yes no no yes yes no yes yes yes
result:
ok 10 token(s): yes count is 7, no count is 3
Test #15:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
10 142547841254232 47854125478695 14525418745256 25412545659642 66524558844142 96568547411254 14254145517454 35524521455848 14255174526963 11452544121544
output:
yes no yes no no no no yes no yes
result:
ok 10 token(s): yes count is 4, no count is 6
Test #16:
score: 0
Accepted
time: 34ms
memory: 3648kb
input:
10 996491788296388609 998244359987710471 998244361984199177 993244859952713971 993244861939203677 991501065653565109 991501562275991609 996492287418565109 996492786540991609 986535338010991609
output:
yes no no no no no no no yes yes
result:
ok 10 token(s): yes count is 3, no count is 7
Test #17:
score: 0
Accepted
time: 53ms
memory: 3648kb
input:
10 903887901943817851 851247006919432117 919722283032763471 813440365584485521 882865661919651791 910336786263475913 886164039929921029 939010110792302767 870233819457687473 848131007416939777
output:
no no no yes no no no no no no
result:
ok 10 token(s): yes count is 1, no count is 9
Test #18:
score: 0
Accepted
time: 43ms
memory: 3704kb
input:
10 835340052889887691 882050214742719557 956200700734221251 904169343239304203 863340778844950207 891950196387379699 828795647431900943 859506290505387449 899701754897659979 864812216762014253
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #19:
score: 0
Accepted
time: 64ms
memory: 3780kb
input:
10 937045348389519233 917861821069527241 853830881092139933 925942273470477919 864192191576296049 924924805832632331 922601114604837757 865189184621142377 810915387784069681 888699713123099173
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #20:
score: 0
Accepted
time: 39ms
memory: 3652kb
input:
10 954695934802062421 928293474552035987 881887067877256247 883003085267505011 912334294055532781 905004098122367039 904611857774338939 865050043975560907 866170490664542059 878270013492173387
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #21:
score: 0
Accepted
time: 50ms
memory: 3696kb
input:
10 863287381806610583 897060909503816381 847532274494783321 916539028167187829 948518075135486161 892501899295334311 970235035102296793 837318859665480457 915965457572353379 895158157552955773
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #22:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
10 919302001859835031 947340380138089009 900556914498219493 969704550604426279 956992278889442207 987516654128597423 918322478734791233 931103932576667281 969704550604426279 912231986741863301
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #23:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
10 986944548782890903 923962410451485991 952106884898696959 907530076115634017 976681729160218187 992802037127004589 942660210777127993 902827937085172543 922822560806710309 910720471852200869
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #24:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
10 977938944616392739 991018971487700887 959433565239483101 938750532582460177 945778797339850751 976877969599178197 940145114745959443 965499754836427177 977353167106372817 920763506622625117
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #25:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
10 932214518129214889 909898103783887369 956740019766652469 921494971682440147 986908544799827189 946604456289732613 924189644989672057 933389877512177959 973338438985234457 913889519530749173
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #26:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
10 994056263547575957 919379339693933303 985741487233972009 919379339693933303 941097907430752373 994056263547575957 939407689956239011 967464086825851847 933164994772745347 922924266205383287
output:
no no no no no no no no no no
result:
ok 10 token(s): yes count is 0, no count is 10
Test #27:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
2 1 1000000000000000000
output:
no yes
result:
ok 2 token(s): yes count is 1, no count is 1
Extra Test:
score: 0
Extra Test Passed