两个 long long 相乘时应转为 __int128 吧？
by MichaelLee @ 2022-08-15 09:57:30
@[MichaelLee](/user/288135) $\texttt{But \ It's \ Still\ TLE}$
by Link_Cut_Y @ 2022-09-14 22:12:41
LL qpow(LL a, LL b, LL p) {
LL res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
这里写挂了，两个long long相乘会溢出，导致米勒罗宾把素数判断成非素数，然后硬上pollard-rho死循环了
by cats142857 @ 2022-09-22 22:15:30
@[cats142857](/user/721928) 全都改成 $int128$ 了，但是还是不对。
```
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <ctime>
#define LL __int128
using namespace std;
const LL test[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
LL ans = -0x3f3f3f3f;
int T;
LL n;
namespace Fread {
const int SIZE = 1 << 21; char buf[SIZE], *S, *T;
inline char getchar() { if (S == T) { T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n'; } return *S ++ ; }
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() { fwrite(buf, 1, S - buf, stdout); S = buf; }
inline void putchar(char c) { *S ++ = c; if (S == T) flush(); }
struct NTR { ~ NTR() { flush(); } } ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
template<typename T>
Reader& operator >> (T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } x = 0;
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } x *= f;
return *this;
}
Reader& operator >> (char& c) {
c = getchar(); while (c == ' ' || c == '\n') c = getchar();
return *this;
}
Reader& operator >> (char* str) {
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
while (c != ' ' && c != '\n' && c != '\r') { str[len++] = c; c = getchar(); }
str[len] = '\0';
return *this;
}
Reader(){}
} cin;
const char endl = '\n';
struct Writer {
template<typename T>
Writer& operator << (T x) {
if (x == 0) { putchar('0'); return *this; }
if (x < 0) { putchar('-'); x = -x; }
static int sta[45]; int top = 0;
while (x) { sta[++top] = x % 10; x /= 10; }
while (top) { putchar(sta[top] + '0'); --top; }
return *this;
}
Writer& operator << (char c) {
putchar(c);
return *this;
}
Writer& operator << (char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
namespace Functions {
LL abs(LL x) { return x < 0 ? -x : x; }
LL gcd(LL a, LL b) {
return !b ? a : gcd(b, a % b);
}
LL qpow(LL a, LL b, LL p) {
LL res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
LL mul(LL a, LL b, LL p) {
LL res = 0;
while (b) {
if (b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}
bool Miller_Rabin(LL n) { // ÅÐ¶Ï n ÊÇ·ñÊÇÖÊÊý
if (n == 1) return false;
LL t = n - 1, k = 0;
while (!(t & 1)) t >>= 1, k ++ ;
for (int i = 0; i < 9; i ++ ) {
if (n == test[i]) return true;
LL a = qpow(test[i], t, n), ne = a;
for (int i = 1; i <= k; i ++ ) {
ne = a * a % n;
if (ne == 1 && a != 1 && a != n - 1) return false;
a = ne;
}
if (a != 1) return false;
}
return true;
}
}
using namespace Functions;
LL Pollard_Rho(LL n) { // ·Ö½â n
if (n == 4) return 2;
if (Miller_Rabin(n)) return n;
LL c = rand() % (n - 1) + 1;
auto f = [=](LL x) {return (mul(x, x, n) + c) % n; };
LL x = f(c), y = f(f(c));
for (int lim = 1; x != y; lim = min(lim << 1, 128)) {
LL cnt = 1;
for (int i = 0; i < lim; i ++ ) {
cnt = mul(cnt, abs((x - y) % n), n);
if (!cnt) break;
x = f(x), y = f(f(y));
}
if (gcd(cnt, n) != 1) return gcd(cnt, n);
}
return n;
}
void max_factor(LL n) {
if (Miller_Rabin(n))
return ans = max(ans, n), void();
LL d = Pollard_Rho(n);
while (d == n) d = Pollard_Rho(n);
if (Miller_Rabin(d)) ans = max(ans, d);
else max_factor(d);
d = n / d;
if (Miller_Rabin(d)) ans = max(ans, d);
else max_factor(d);
}
int main() {
srand(time(0));
cin >> T;
while (T -- ) {
cin >> n;
ans = -0x3f3f3f3fll;
if (Miller_Rabin(n)) puts("Prime");
else max_factor(n), cout << ans << endl;
}
return 0;
}
```
by Link_Cut_Y @ 2022-10-30 12:25:41