代码笔记_数学知识

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

代码笔记_数学知识

作者：

zqiceberg , 2020-01-17 07:00:06 , 所有人可见 , 阅读 1032

1

6

2147483748
sqrt(2 x 10^9),大约在40000-50000
1- (2^31 - 1)约数个数最多的数有多少个 1600
2 x 10^9 约数个数最多的数有多少个 1536
(LL)c * x，两个数相乘的时候，取个LL，避免爆掉

`三大模板`

线性筛

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    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] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

最大公约数

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

快速幂

求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

`质数`

AcWing 866. 试除法判定质数
AcWing 867. 分解质因数
AcWing 868. 筛质数
AcWing 1292. 哥德巴赫猜想
AcWing 1293. 夏洛克和他的女朋友
AcWing 196. 质数距离

`约数`

AcWing 869. 试除法求约数
AcWing 870. 约数个数208
AcWing 871. 约数之和
AcWing 872. 最大公约数
AcWing 197. 阶乘分解
AcWing 1291. 轻拍牛头
AcWing 1294. 樱花
AcWing 198. 反素数
AcWing 200. Hankson的趣味题