QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648577#8103. Productrotcar07ML 7ms7732kbC++23823b2024-10-17 19:34:132024-10-17 19:34:13

Judging History

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

  • [2024-10-17 19:34:13]
  • 评测
  • 测评结果:ML
  • 用时:7ms
  • 内存:7732kb
  • [2024-10-17 19:34:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int lim=3e5;
vector<ll> V;
int k;ll p[105],n;
int main(){
    cin>>k>>n;for(int i=1;i<=k;i++) cin>>p[i];
    int cur=0;V.push_back(1);
    while(++cur<=k){
        ll z=p[cur];
        for(int i=0;i<V.size()&&V.size()<lim;i++){
            if(V[i]*z<=n) V.push_back(V[i]*z);
        }
        if(V.size()>=lim) break;
    }
    ll ans=0;
    sort(V.begin(),V.end());
    auto dfs=[&](auto dfs,int id,ll x) -> void {
        if(n/x*x<ans) return;
        if(id>=cur){
            while(x<=n){
                dfs(dfs,id-1,x);
                x*=p[id];
            }
        }
        else{
            ans=max(ans,x**(upper_bound(V.begin(),V.end(),n/x)-1));
        }
    };
    dfs(dfs,k,1);
    cout<<ans<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 30
2 3 7

output:

28

result:

ok 1 number(s): "28"

Test #2:

score: 0
Accepted
time: 7ms
memory: 7732kb

input:

7 939341491978215167
2 3 19 43 47 53 61

output:

939207819748596228

result:

ok 1 number(s): "939207819748596228"

Test #3:

score: -100
Memory Limit Exceeded

input:

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

output:

997257095125632000

result: