Đề 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:
- using namespace std;
- #define ll long long
- ll n,k;
- bool check(ll v){
- ll kk=1;
- ll res=0;
- while(v>=kk){
- res=res+(v/kk);
- kk=kk*k;
- }
- if(res>=n) return true;
- return false;
- }
- int main(){
- cin>>n>>k;
- ll low = 0 , high = 1000000000000000000,mid;
- while(low<high){
- mid=(low+high)/2;
- if(check(mid)) high=mid;
- else low=mid+1;
- }
- cout<<low;
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét