Editorial for VM 14 Bài 03 - Aladdin và cây đèn cầy


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define qword unsigned long long

using namespace std;

qword n;
//* a candle is off only if it has an odd number of factors
//* -> its ID must be a perfect square

int main() {
  cin >> n;
  qword l = 1, r = 2 * (qword)1e18, ans = 0;
  while (l <= r) {
    qword mid = l + r >> 1;
    if (mid - (qword)((long double)sqrt((long double)mid) + 1e-18) >= n) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  cout << ans << endl;
  return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define SQR(x) ((x)*(x))
using namespace std;
typedef long long ll;
const ll INF=(ll)2e18+7LL;
ll truncsqrt(ll x) {
    ll t=floor(sqrt(x));
    FOR(i,-5,5) if (t+i>=0 && SQR(t+i)>x) return (t+i-1);
}
ll count(ll x) {
    return (x-truncsqrt(x));
}
void process(void) {
    ll k;
    cin>>k;
    ll l=1;
    ll r=INF;
    while (true) {
        if (l==r) {
            cout<<l;
            return;
        }
        if (r-l==1) {
            if (count(l)>=k) cout<<l; else cout<<r;
            return;
        }
        ll m=(l+r)>>1;
        if (count(m)>=k) r=m; else l=m+1;
    }
}
int main(void) {
    process();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.