QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355369#8103. Productucup-team004#ML 0ms3600kbC++201.7kb2024-03-16 16:32:052024-03-16 16:32:07

Judging History

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

  • [2024-03-16 16:32:07]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3600kb
  • [2024-03-16 16:32:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll =  long long;
using i64 =  long long;
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define PI pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back

constexpr int P = 100;
vector<int> pri;
bool isprime[P + 1];
map<ll,PI> M;
int k;
ll n,ans;
void dfs(int p,ll x){
    if(p==pri.size()){
        auto t=M.upper_bound(-x);
        ll tmp=1;
        if(t!=M.begin()){
            t--;
            //cerr<<t->fi<<" "<<t->se.fi<<endl;
            tmp=t->se.fi;
        }
        ans=max(x*tmp,ans);
        return;
    }
    dfs(p+1,x);
    if(n/pri[p]>=x)dfs(p,x*pri[p]);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::fill(isprime + 2, isprime + P + 1, true);
    std::vector<int> primes;
    for (int i = 2; i <= P; i++) {
        if (!isprime[i]) {
            continue;
        }
        primes.push_back(i);
        for (int j = i * i; j <= P; j += i) {
            isprime[j] = false;
        }
    }

    //std::cerr << primes.size() << "\n";
    cin>>k>>n;
    For(i,1,k){
        int t;
        cin>>t;
        pri.pb(t);
    }
    sort(pri.begin(),pri.end());
    int t=min((int)pri.size(),11);
    M[-n]=mp(1,0);
    for(auto it=M.begin();it!=M.end();it++){
        int dq=it->se.se;
        ll x=it->se.fi;
        //cerr<<it->fi<<" "<<dq<<" "<<x<<endl;
        for(int i=dq;i<t&&n/pri[i]>=x;i++){
            ll nx=x*pri[i];
            if(!M.count(-n/nx)||M[-n/nx].fi<nx){
                M[-n/nx]=mp(nx,i);
            }
        }
    }  
    dfs(t,1);
    cout<<ans<<endl;
    // int k;
    // i64 N;
    // std::cin >> k >> N;



    return 0;
}

詳細信息

Test #1:

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

input:

3 30
2 3 7

output:

28

result:

ok 1 number(s): "28"

Test #2:

score: -100
Memory Limit Exceeded

input:

7 939341491978215167
2 3 19 43 47 53 61

output:

939207819748596228

result: