問題描述

給定一個大小為 $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<bits/stdc++.h>
#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)$。