对数和最小公倍数

对数取整

以2为底取整的对数等价于2进制最高位是多少. 几种方法:

  1. 循环

  2. 两次翻转

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    inline uint32_t
    reverse(uint32_t x)
    {
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) << 16);
    return x;
    }

  3. 汇编

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    inline uint32_t
    bsr_highest_bit(uint32_t x)
    {
    if (!x) return 0;
    uint32_t bit;
    asm(
    "bsr %1, %0"
    : "=r" (bit)
    : "r" (x)
    );
    return (1 << bit);
    }

参考链接

reverse解析

对数小数

参考链接

1-N的最小公倍数

素数打表,然后求$ prodlimits_{i = 1}^{n} P_{i}^{lfloor log_{P_{i}}Nrfloor} $ ,求对数的部分截止到$sqrt [] n$即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int MAX=1e6;
const int MOD=1e9+7;
int notPrime[MAX];
int (int x, int n) {
unsigned long long base=x,ans=1;
for(;n;n>>=1){
if(n&1)
ans=(ans*base)%MOD;
base=(base*base)%MOD;
}
return (int)ans;
}
void primes(int n){
memset(notPrime,0, sizeof(notPrime));
for(int i=4;i<n;i+=2)
notPrime[i]=true;
for(int i=3;i<n;i+=2)
if(!notPrime[i])
for(int j=i*i;j<n;j+=2*i)
notPrime[j]=true;
}
int solve(int n){
int ans=1,range =(int)sqrt(n);
double base = log(n);
primes(n);
for(int i=2;i<n;i++)
if(!notPrime[i])
if(i<range)
ans*=fastPow(i,(int)(base/log(i)));
else
ans*=i;
return ans;

}