Codeforces Round #125 (Div. 一 A)

http://codeforces.ru/contest/198/problem/A

Problem

一个数x，起初x＝1，然后，每次进行x=x*k+b操作，进行n次，得到一个数z。现在，给一个数y，起初y=t，然后进行y=y*k+b操作，问至少进行多少次使得$z\leq y$。

数据范围

$1\leq k,b,n,t\leq 10^6$，单case

Solution

会发现$z=k^n+bk^{n-1}+...+bk+b$，假设进行了m次，$m\leq n$，$y=tk^m+bk^{m-1}+....+bk+b$，发现，z和y都含有$bk^{m-1}+...+bk+b$，那么只需要比较前面，由于是单case，可以采用枚举m的方法（显然只需枚举$m<n$），想办法判断当前 $k^n+bk^{n-1}+...+bk^m\leq tk^m$，能否成立即可。先特判m=0和k=1的情况，而判断只需log级别判断。如果都不成立，则m=n。

如果多case怎么办呢？其实有常数级别的办法。

$z=k^n+bk^{n-1}+...+bk+b$

$y=tk^m+bk^{m-1}+....+bk+b$

考虑什么时候$z\leq y$？

$z-y=k^n+b(k^{n-1}+...+k^m)-tk^m\leq 0$

$k^n+b(k^{n-1}+...+k^m)\leq tk^m$

$k^n + b \frac{k^n-k^m}{k-1}\leq tk^m$

两边乘以k-1

$(k-1)k^n+b(k^n-k^m)\leq (k-1)tk^m$

$(k-1+b)k^n\leq (t(k-1)+b)k^m$

两边取对数函数`

$\lg(k-1+b)+n\lg(k)\leq \lg(t(k-1)+b)+m\lg(k)$

转换一下

$\lg(k-1+b)+n\lg(k)-\lg(t(k-1)+b)\leq m\lg(k)$

问题转换为，求上述公式的最小m。整体复杂度是常数级别的，据说c++的lg函数是log级别的？… 这样多case也能过啦。

My code

//Hello. I'm Peter.
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define MAXN
#define N
#define M 35
ll k,b,n,t,m;
const double eps=1e-9;
int dcmp(double x){
    if(fabs(x)<eps) return 0;
    else if(x<0) return -1;
    else return 1;
}
int main(){
    cin>>k>>b>>n>>t;
    if(k==1){
        ll t1=n*b+1;
        t1-=t;
        if(t1<=0) cout<<0<<endl;
        else{
            ll ans=t1/b;
            if(ans*b!=t1) ans++;
            cout<<ans<<endl;
        }
        exit(0);
    }
    double y;
    y=log(k-1+b)+n*log(k)-log(t*(k-1)+b);
    if(y<0) m=0;
    else{
        m=y/log(k);
        if(dcmp(m*log(k)-y)<0) m++;
    }
    cout<<m<<endl;
    return 0;
}