QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#335980#8103. Productucup-team1209#TL 159ms7536kbC++201.3kb2024-02-24 10:51:222024-02-24 10:51:22

Judging History

你现在查看的是最新测评结果

  • [2024-02-24 10:51:22]
  • 评测
  • 测评结果:TL
  • 用时:159ms
  • 内存:7536kb
  • [2024-02-24 10:51:22]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = __uint128_t;
using i128 = __int128_t;
std::vector<int> ps;
const int M = 5e5;

u64 pms[M];
int cc;

ll n;

bool ins(u64 x) {
	for(int i = 0;i < cc;++i) {
		if((i128) pms[i] * x <= n) {
			if(cc == M) {
				return 0;
			}
			pms[cc++] = pms[i] * x;
		}
	}
	return 1;
}
int idx;

ll check(ll n) {
	for(int i : ps) {
		for(;(u64)n % (u32)i == 0;) n /= i;
	}
	return n == 1;
}
ll ans = 1;
void dfs(ll x, int id) {
	if(id < idx) {
		ll z = std::upper_bound(pms, pms + cc, n / x)[-1];
		ans = std::max(ans, z * x);
		return ;
	}
	for(;;) {
		dfs(x, id - 1);
		if((i128)x * ps[id] > n) {
			break;
		}
		x *= ps[id];
	}
}
void guess(ll n) {
	for(int i = 0;i < 2e5 && !check(n);--n, ++i);
	if(check(n)) {
		cout << n << '\n';
		exit(0);
	}
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	int k; cin >> k >> n;
	ps.resize(k);
	for(int & x : ps) cin >> x;
	guess(n);
	*pms = 1, cc = 1;
	sort(ps.begin(), ps.end());
	for(idx = 0;idx < (int) ps.size();++idx) {
		if(!ins(ps[idx])) break;
	}
	std::sort(pms, pms + cc);
	dfs(1, ps.size() - 1);
	cout << ans << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3644kb

input:

3 30
2 3 7

output:

28

result:

ok 1 number(s): "28"

Test #2:

score: 0
Accepted
time: 25ms
memory: 6272kb

input:

7 939341491978215167
2 3 19 43 47 53 61

output:

939207819748596228

result:

ok 1 number(s): "939207819748596228"

Test #3:

score: 0
Accepted
time: 57ms
memory: 7524kb

input:

16 997257405471326207
2 3 5 11 19 23 37 41 47 53 59 61 73 79 89 97

output:

997257095125632000

result:

ok 1 number(s): "997257095125632000"

Test #4:

score: 0
Accepted
time: 159ms
memory: 7524kb

input:

21 999404092522162547
2 3 13 17 19 23 29 31 37 41 43 47 59 61 67 71 73 79 83 89 97

output:

999404022916180674

result:

ok 1 number(s): "999404022916180674"

Test #5:

score: 0
Accepted
time: 33ms
memory: 7536kb

input:

6 969452367537798143
2 3 5 7 11 13

output:

969402569554298880

result:

ok 1 number(s): "969402569554298880"

Test #6:

score: -100
Time Limit Exceeded

input:

25 999949383078942015
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

output:


result: