Thứ Tư, 18 tháng 11, 2020

Tìm v nhỏ nhất thỏa mãn v+[v/k]+...+[v/k^x]>=n thỏa mãn [v/k^x]=0

 Đề bài: $\href{https://codeforces.com/problemset/problem/165/B}{Đây}$

Tóm tắt: Cho hai số n và k. Tìm số v nhỏ nhất thỏa mãn: v+[v/k]+[v/k^2]+... >=n.

Lời giải: Ở bài này, ý tưởng là ta sẽ dùng chặt nhị phân đơn thuần.

Source:

  1. using namespace std;
  2. #define ll long long
  3. ll n,k;
  4. bool check(ll v){
  5. ll kk=1;
  6. ll res=0;
  7. while(v>=kk){
  8. res=res+(v/kk);
  9. kk=kk*k;
  10. }
  11. if(res>=n) return true;
  12. return false;
  13. }
  14. int main(){
  15. cin>>n>>k;
  16. ll low = 0 , high = 1000000000000000000,mid;
  17. while(low<high){
  18. mid=(low+high)/2;
  19. if(check(mid)) high=mid;
  20. else low=mid+1;
  21. }
  22. cout<<low;
  23. return 0;
  24. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...