扩展翡蜀定理问题

问题描述

给定一个大小为 $n$ 的集合 A = { a 1 , a 2 ∼ a n } A=\{a_1,a_2 \sim a_n\} A={a1​,a2​∼an​}，满足条件 $\text{gcd}(A)=1$。

$O(1)$时间内 求最大的 $k$ ，满足不存在一个大小为 $n$ 的非负数集合 B = { b 1 , b 2 … b n } B=\{b_1,b_2 \ldots b_n\} B={b1​,b2​…bn​}使得 ${\sum }_{i=1}^{i\le n}{a}_i\times b_i=k$

数据约束：$a_i\le 10^9$

问题解决

很遗憾，具体怎么解决我还不会，这里只能给出一点我已知的，有可能对解决问题有帮助的东西。

一.暴力代码

时间复杂度 $O(爆炸)$ ， 空间复杂度 $O(爆炸)$。

只能用来求最终答案在 $10^8$ 以内的数据。

#include
#define ll long long
using namespace std;
ll a[100000005],q,vist[100000005];
signed main(){
	ios::sync_with_stdio(false);
	cin>>q;
	for(ll i=1;i<=q;i++)cin>>a[i];
	vist[0]=1;
	for(ll i=0;i<=100000000;i++){
		if(vist[i])for(ll j=1;j<=q;j++)vist[i+a[j]]=1;
	}
	for(ll i=100000000;i>=1;i--){
		if(vist[i]==0){
			cout<<i;
			break;
		}
	}
	return 0;
}

二.考虑 $b_i$ 可以为负数的情况

对于任意 $k$ 都存在一个大小为 $n$ 的整数集合 B = { b 1 , b 2 … b n } B=\{b_1,b_2 \ldots b_n\} B={b1​,b2​…bn​}使得 ${\sum }_{i=1}^{i\le n}{a}_i\times b_i=k$

这里给出一个构造大小为 $n$ 的整数集合的代码。

时间复杂度：$O(nlog(n))$，空间复杂度 $O(n)$。

写不动了，先鸽着。