高罢
by fjy666 @ 2021-12-05 13:16:28
e~
by dingshengyang @ 2021-12-05 13:23:47
肯定不能。
by Imitators @ 2021-12-05 13:24:22
pow 的效率都够低了。。。
by shyr @ 2021-12-05 13:28:24
再说朴素 $\operatorname{O}(\log n)$ 不比你带个二分强得多?
by shyr @ 2021-12-05 13:29:39
@[Respons_](/user/357163) 这是$\log \log n$,pow是O(1)的
by dingshengyang @ 2021-12-05 13:37:54
@[Respons_](/user/357163)
```cpp
#include <bits/stdc++.h>
#define R register
#define inl inline
#define fastios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define Debug(file) freopen(file".in","r",stdin);freopen(file".out","w",stdout);
using namespace std;
namespace my_lib{
typedef long long LL;
static int primes[5761456],cnt=0,st[10000000];
class MATH{public:
LL __gcd_(LL a,LL b){
return b==0?a:__gcd_(b,a%b);
}inline LL __lcm_(LL a,LL b){
return a/__gcd_(a,b)*b;
}inline int __lg2_(LL num){
LL l = 0,r = 60;
while(l<r){
LL mid = (l + r + 1) >> 1;
if(pow(2,mid) > num)r = mid - 1;
else l = mid;
}
return (int)l;
}inline int cnt_d(LL n){
const int N = 1e9+7;
unordered_map<int,int> hash;
for(int i = 2;i <= n/i;i ++){
while(n%i==0){
n/=i;
hash[i]++;
}
}
if(n>1)hash[n]++;
long long ans = 1;
for(auto i:hash){
ans = ans*(i.second+1)%N;
}
return ans;
}inline void init(int n = 1e7){
for(int i = 2;i <= n;i ++){
if(!st[i]) primes[cnt++] = i;
for(int j = 0;primes[j]<=n/i;j++){
st[primes[j]*i] = 1;
if(i%primes[j]==0)break;
}
}
}
}math;
}using namespace my_lib;
const int N = 5e6;
inline int pp_lg2(LL n){
int p = 0;
while(1<<p<n)p++;
return --p;
}
int main() {
/*for(int i = 0;i < N;i ++)pp_lg2(2147483648);//TLE*/
/*for(int i = 0;i < N;i ++)math.__lg2_(2147483648);//665ms*/
return 0;
}
```
by dingshengyang @ 2021-12-05 13:42:00
@[dingshengyang](/user/302394) pow是O(1)的?不用函数你怎么求幂?以及一个二分怎么就变成loglogn了?
不过log2函数追求更好的复杂度有啥意义?暴力顶多才六七十次……(不算高精)
还有就是$lg2 = log_{10}2$
by 江户川コナン @ 2021-12-05 13:45:42
当然,log2仅要110ms,事实证明,他是O(1)的,比O(6)快
by dingshengyang @ 2021-12-05 13:46:57
yysy,pp_lg2 写错了八。
by cnyzz @ 2021-12-05 13:48:37