首页 > itarticle > 对数和最小公倍数

对数和最小公倍数

admin 11月 13, 2020 0

对数取整

以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;

}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能