Bình luận

• 
  

  2

  

  pppssslc  đã bình luận lúc 30, Tháng 5, 2025, 2:45 ← sửa 8 →

  spoil!!!

  Nhận xét:

  • ~n ≤ 10^{18}~ nên ~p_1 × p_2 × p_3 ≤ 10^{18}~
  • GS: ~10^6 < p_1 < p_2 < p_3~ → ~p_1 × p_2 × p_3 > 10^6~ → vô lí.
    → ta chỉ xét các bộ 3 số nguyên tố liên tiếp ~(p_1, p_2, p_3)~ với ~p_1<10^6~.

  Để ~m~ có đúng ~k~ ước thì:

  ~k = (t_1 + 1) × (t_2 + 1) × (t_3 + 1)~

  Vậy nên, ta sẽ:

  • Sàng các số nguyên tố tới ~10^6+20~.
  • Duyệt các bộ ba số nguyên tố liên tiếp:

  Với mỗi bộ ba ta sẽ thử từng bộ số ~(i, j, p)(2 ≤ i, j, p ~ và ~ i × j × p = k)~.

  Lưu ý:

  Nhớ xử lí tràn số.

  Code mẫu:

  #include<bits/stdc++.h>
  #define str string
  #define ll unsigned long long
  #define db double
  #define pii pair<int, int>
  #define piii pair<int, pii>
  #define piiii pair<pii, pii>
  #define se second
  #define fi first
  #define vi vector<int>
  #define vii vector<vector<int>>
  #define mpii map<int, int>
  #define umpii unordered_map<int, int>
  #define si set<int>
  #define usa unordered_set<int>
  #define mulsi multiset<int>
  using namespace std;
  
  const int mod=1e9+7;
  const int maxn=1e6+5;
  
  ll n, ans; int k;
  vector<ll> prime;
  bitset<maxn> isprime;
  
  void init(){
    for(int i=2; i*i<maxn; ++i)if(isprime[i]==0){
        for(int j=i*i; j<=maxn; j+=i)
            isprime[j]=1;
    }
    for(int i=2; i<maxn; ++i)if(isprime[i]==0)prime.push_back(i);
  }
  
  ll mul(ll a, ll b){
    if(a==0 || b==0)return 0;
    if(a>n/b)return n+1;
    return a*b;
  }
  
  ll binpow(ll n, int k){
    if(k==0)return 1;
    ll a=binpow(n, k/2);
    if(k%2==0)return mul(a, a);
    else return mul(mul(a, a), n);
  }
  
  int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    init();
    cin>>n>>k;
    vector<piii> div;
    for(int i=2; i<=57; ++i)
          for(int j=2; j<=57; ++j)
              for(int p=2; p<=57; ++p)
                  if(i*j*p==k)
                      div.push_back({i, {j, p}});
    for(int i=0; i<prime.size()-2; ++i)for(piii x: div){
        ll pow1=binpow(prime[i], x.fi-1);
        ll pow2=binpow(prime[i+1], x.se.fi-1);
        ll pow3=binpow(prime[i+2], x.se.se-1);
        ll m=mul(pow1, mul(pow2, pow3));
        if(m<=n && m>ans) ans=m;
    }
    cout<<ans;
    return 0;
  }
  

  Lưu ý:

  Lời giải chỉ mang tính tham khảo nên đừng ai copy lời giải này.