TLE10pts求助
查看原帖
TLE10pts求助
527730
MafuyuQWQ楼主2025/2/8 15:38
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 300010, inf = 1e7;

mt19937 rnd(time(0));

int res;
int pr[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

int quick_power(int a, int b, int p)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = (__int128)a * res % p;
		a = (__int128)a * a % p;
		b >>= 1;
	}
	
	return res;
}

bool MR(int p)
{
	for (int i = 1; i <= 12; i ++ ) 
		if (p == pr[i]) return true;
	if (p < 40) return false;
	int x;
	for (int i = 1; i <= 12; i ++ )
	{
		x = pr[i];
		if (quick_power(x, p - 1, p) != 1) return false;
		int r = p - 1;
		while (r % 2 == 0) 
		{
			r >>= 1;
			int qp = quick_power(x, r, p);
			if (qp == p - 1) return true;
			else if (qp != 1) return false;
		}
	}
		
	return true;
}

int PR(int x)
{
	if (MR(x)) return x;
	if (x == 4) return 2;
	
	while (true)
	{
		int c = rnd() % (x - 1) + 1;
//		cerr << c << '\n';
		auto f = [=](int n) { return ((__int128)n * n + c) % x; };
		int a = f(0), b = f(a), p = 1, q;
		for (int lim = 1; lim < 256 && a != b; lim <<= 1)
		{
			for (int i = 0; i < lim; i ++ )
			{
				if (a == b) break;
				q = p * abs(a - b) % x;
				if (!q) break;
				p = q;
				a = f(a), b = f(f(b));
			}
			int d = __gcd(x, p);
			if (d > 1) return d;
		}
	}
}

void F(int x)
{
    if (x <= res || x < 2) return;
    if (MR(x))
    {
        res = max(res, x);
        return;		
    }
    int p = x;
    while (p >= x) p = PR(x);
    while (x % p == 0) x /= p;
    F(x), F(p);
}

signed main()
{
	int T;
	cin >> T;
	while (T -- )
	{
		int n;
		cin >> n;
		
		res = 0;
		if (MR(n)) cout << "Prime\n";
		else F(n), cout << res << '\n';
	}
	
	return 0;
}
2025/2/8 15:38
加载中...