Bình luận

• 
  

  1

  

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

  spoil!!!

  Nhận xét:

  • n ≤ 1e18 nên p1 × p2 × p3 ≤ 1e18
  • GS: 1e6 < p1 < p2 < p3 => p1 × p2 × p3 > 1e18 => vô lí.
    => ta chỉ xét các bộ 3 số nguyên tố liên tiếp (p1, p2, p3) với p1<1e6.

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

  k = (t1 + 1) × (t2 + 1) × (t3 + 1)

  Vậy nên, ta sẽ:

  • Sàng các số nguyên tố tới 1e6+20.
  • Duyệt các bộ 3 số nguyên tố liên tiếp:

  Với mỗi bộ 3 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;
  }