Mess

在满足时间复杂度下，代码果然还是越简单越好

今天写了个判断一个数的k次方是否超过另个数
然后当时想都没想就用了快速幂
(其中那个数的k次方可能超过long long)

第一个版本：判断x ^ n 是否大于m

1
2
3
4
5
6
7
8
9
10
11
bool pow(ll x,ll n,ll m){  
    ll res = 1;  
    while(n > 0){  
        if(n & 1) res = res * x;  
        x = x*x;  
        n>>=1;  
        if(res >= m) return true;  
    }  
    if(res >= m) return true;  
    else return false;  
}

下面这样是错的。。因为数据一大x超过long long 变成0，res也从1变成了0.
例子是：1000 536870912 1000

试了试加了个条件。x > m跳出。

1
2
3
4
5
6
7
8
9
10
11
bool pow(ll x,ll n,ll m){  
    ll res = 1;  
    while(n > 0){  
        if(n & 1) res = res * x;  
        x = x*x;  
        n>>=1;  
        if(res >= m || x>=m) return true;  
    }  
    if(res >= m) return true;  
    else return false;  
}

发现还是错了，看这组数据：3 2 1

还需要再加个条件。。n>0.因为可能n已经为0了但是x大于了m.

1
2
3
4
5
6
7
8
9
10
11
bool pow(ll x,ll n,ll m){  
    ll res = 1;  
    while(n > 0){  
        if(n & 1) res = res * x;  
        x = x*x;  
        n>>=1;  
        if(res >= m || (n > 0 && x >= m)) return true;  
    }  
    if(res >= m) return true;  
    else return false;  
}

其实这个东西不写快速幂就很快了，指数函数式爆炸上升的。。手残写了快速幂还错。。下次要牢记啊。