为啥会TLE,本地过会TLE的数据
查看原帖
为啥会TLE,本地过会TLE的数据
700558
williamwei楼主2024/8/10 10:13
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int M = 2e5;
const int B = 86;
const int N = 200;
const int L = 25;
int t, n, tot, p[maxn];
ll x, res[B][B];
bool F, v[maxn];
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return (ll)a * b / gcd(a, b);}
int query(int a, int b) {
    cout << "? " << a << ' ' << b << endl;
    cin >> x; return x;
}
bool check(int a, int b, int c) {
	if (!F && lcm(a, b) == res[1][2] && lcm(b, c) == res[2][3] && lcm(a, c) == res[1][3])
		cout << "! " << a << ' ' << b << ' ' << c << endl, F = true;
}
int main() {
    cin >> t; srand(20101008);
    for (int i = 2; i <= M; i++) {
		if (!v[i]) p[++tot] = i;
		for (int j = 1; j <= tot && i * p[j] <= M; j++) {
			v[i * p[j]] = true; 
			if (i % p[j] == 0) break;
		}
	}
    while (t--) {
        cin >> n;
        if (n < B) {
            for (int i = 1; i < n; i++)
                for (int j = i + 1; j <= n; j++)
                    res[i][j] = res[j][i] = query(i, j);
            if (n == 3) {
            	F = false; for (int i = 1; i <= M && !F; i++)
            		check(i, i + 1, i + 2), check(i, i + 2, i + 1), check(i + 1, i + 2, i), check(i + 1, i, i + 2), check(i + 2, i, i + 1), check(i + 2, i + 1, i);
                continue;
            }
            cout << "! ";
            for (int i = 1; i <= n; i++) {
                ll cur = 0;
                for (int j = 1; j <= n; j++)
                    if (i != j) cur = gcd(cur, res[i][j]);
                cout << cur << ' ';
            } cout << endl;
        } else {
        	int res = 0, P = 0;
			for (int i = 1; i <= N; i++) {
				ll cur = 0, p = rand() % n + 1;
				for (int j = 1; j <= L; j++) {
					int v = rand() % n + 1;
					while (v == p) v = rand() % n + 1;
					cur = gcd(cur, query(p, v));
				}
				if (!v[cur] && cur > res) res = cur, P = p;
			}
			cout << "! ";
			for (int i = 1; i <= n; i++)
				cout << (i == P ? res : query(i, P) / res) << ' ';
			cout << endl;
		}
    }
    return 0;
}
2024/8/10 10:13
加载中...