AcWing 数学知识_小言_互联网的博客

AcWing 数学知识

2023-01-04 20:22 323人阅读评论(0)

质数

模板：

// 试除法判断质数
bool is_prime(int x)
{
   
    if (x < 2) return false;
    //只需枚举一部分 使得 i<= x / i, 时间复杂度为√n
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

// 试除法分解质因数
void divide(int n)
{
   
    for (int i = 2; i <= n / i; i++)
    {
   
        if (n % i == 0)
        {
   
            int cnt = 0;
            while (n % i == 0)
            {
   
                n /= i;
                cnt++;
            }
            printf("%d %d\n", i, cnt);
        }
    }
    
    //本身就是质数
    if (n > 1) printf("%d %d\n", n, 1);
    printf("\n");
}

//

试除法判定质数

代码：

#include<iostream>
using namespace std;
int n;

bool is_prime(int x)
{
   
    if (x == 1) return false;
    for (int i = 2; i <= x / i; i++)
    {
   
        if (x % i == 0) return false;
    }
    
    return true;
}

int main()
{
   
    scanf("%d", &n);
    while (n--)
    {
   
        int a;
        scanf("%d", &a);
        printf(is_prime(a) ? "Yes\n" : "No\n");
    }
    return 0;
}

分解质因数

代码：

#include<iostream>
using namespace std;

void divide(int n)
{
   
    for (int i = 2; i <= n / i; i++)
    {
   
        if (n % i == 0)
        {
   
            int cnt = 0;
            while (n % i == 0)
            {
   
                n /= i;
                cnt++;
            }
            printf("%d %d\n", i, cnt);
        }
    }
    
    //本身就是质数
    if (n > 1) printf("%d %d\n", n, 1);
    printf("\n");
}

int main()
{
   
    int n;
    scanf("%d", &n);
    
    while (n--)
    {
   
        int a;
        scanf("%d", &a);
        divide(a);
    }
    
    return 0;
}

筛质数

思路：
筛法求质数，有两种方式：

埃氏筛法
线性筛法

埃氏筛法
埃氏筛法每次筛掉质数的倍数（大于等于2倍），这样最后剩下的就全是质数。 $s t [i]$ 为 $f a l se$ 时，表示为质数。

埃氏筛法代码：

#include<iostream>
using namespace std;

const int N = 1000010;
bool st[N];
int primes[N];
int cnt;

void get_primes(int n)
{
   
    for (int i = 2; i <= n; i++)
    {
   
        if (!st[i]) primes[cnt++] = i;
        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
}

int main()
{
   
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    
    return 0;
}

线性筛法
线性筛法保证 $n$ 只会被最小质因子筛掉。

i % primes[j] == 0，primes[j]是i的最小质因子，primes[j]是primes[j] * i的最小质因子。
i % primes[j] != 0，primes[j]小于i的最小质因子，primes[j]是primes[j] * i的最小质因子。

bool st[N];
int primes[N];
int cnt;

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

线性筛法代码：

#include<iostream>
using namespace std;

const int N = 1000010;
bool st[N];
int primes[N];
int cnt;

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 main()
{
   
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    
    return 0;
}

约数

试除法求约数

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;

void get_divisors(int a)
{
   
    vector<int> res;
    for (int i = 1; i <= a / i; i++)
    {
   
        if (a % i == 0)
        {
   
            res.push_back(i);
            // 防止平方根多次出现
            if (i != a / i) res.push_back(a / i);
        }
    }
    
    //从大到小排序
    sort(res.begin(), res.end());
    
    for (int t : res) printf("%d ", t);
    printf("\n");
    
}

int main()
{
   
    scanf("%d", &n);
    while (n--)
    {
   
        int a;
        scanf("%d", &a);
        get_divisors(a);
    }
    return 0;
}

约数个数

思路：
给定一个数 $N$ ， $p_i$ 为 $N$ 的质约数，则可以表示为:
$N=p_{1}^{\alpha_1}\times p_{2}^{\alpha_2} \times p_{3}^{\alpha_3}\times... \times p_{k}^{\alpha_k}$
$N$ 的每一个约数 $d_i$ ，可以表示为:
$d_i=p_{1}^{\beta_1}\times p_{2}^{\beta_2} \times p_{3}^{\beta_3}\times... \times p_{k}^{\beta_k}$
其中， $\le \beta_i \le \alpha_i$ ， $\beta_i$ 的选法有 $\sim \alpha_i$ ，共有 $(\alpha_i + 1)$ 种选法，根据排列组合原理，约数个数为：
$(\alpha_1 + 1) \times (\alpha_2 + 1) \times (\alpha_3 + 1) \times ... \times (\alpha_k + 1)$

依次遍历 $a_i$ ，求 $a_i$ 的质因数以及每个质因数的个数，可以用哈希表保存结果

代码：

#include<iostream>
#include<unordered_map>
using namespace std;

const int mod = 1e9 + 7;


int main()
{
   
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n--)
    {
   
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i++)
        {
   
            while (x % i == 0)
            {
   
                x /= i;
                primes[i]++;
            }
        }
        if (x > 1) primes[x]++;
    }
    
    long long res = 1;
    
    for (auto prime : primes) 
    	res = res * (prime.second + 1) % mod;
    
    cout << res << endl;
    
    return 0;
}

约数之和

思路：
根据约数个数的思路，约数之和为 $d_1 + d_2 + d_3 + ... + d_k \: \: \: ①$
其中， $d_i=p_{1}^{\beta_1}\times p_{2}^{\beta_2} \times p_{3}^{\beta_3}\times... \times p_{k}^{\beta_k} \: \: \: ②$
约数之和为 $(p_1^0+p_1^1+p_1^2...+p_1^{\alpha_1})...(p_k^0+p_k^1+p_k^2...+p_k^{\alpha_k})$
展开可得式①，展开的每一项均为 $d_i$

$(p_i^0+p_i^1+p_i^2...+p_i^{\alpha_1})$ 可以按照下面的方式进行推导：
$t_0 = 1$
$t_1 = t_0 \times p + 1 = p + 1$
$t_2 = t_1 \times p + 1 = p^2 + p + 1$
…
$t_{\alpha_i }= t_{\alpha_i-1} \times p + 1 = p^{\alpha_i } + p^{\alpha_i-1} +... + p + 1$ ，
最后计算 $\displaystyle\prod _{i=1}^n t_{\alpha_i}$ ，即为约数之和。

代码：

#include<iostream>
#include<unordered_map>
using namespace std;

const int mod = 1e9 + 7;


int main()
{
   
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n--)
    {
   
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i++)
        {
   
            while (x % i == 0)
            {
   
                x /= i;
                primes[i]++;
            }
        }
        if (x > 1) primes[x]++;
    }
    
    long long res = 1;
    
    for (auto prime : primes) 
    {
   
        long long t = 1;
        int p = prime.first, a = prime.second;
        while (a--) t = (t * p + 1) % mod;
        res = res * t % mod;
    }
    
    cout << res << endl;
    
    return 0;
}

最大公因数

思路：
欧几里得算法，辗转相除法。
代码：

#include<iostream>
using namespace std;

int gcd(int m, int n)
{
   
    return m % n == 0 ? n : gcd(n, m % n);
}

int main()
{
   
    int n;
    cin >> n;
    while (n--)
    {
   
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }
    return 0;
}

欧拉函数

思路：
互质是公约数只有1的两个整数。在算数基本定理中， $N=p_{1}^{\alpha_1}\times p_{2}^{\alpha_2} \times p_{3}^{\alpha_3}\times... \times p_{m}^{\alpha_m}$ ，根据欧拉函数的定义： $\phi(N) = N \times \cfrac{p_1 - 1}{p_1} \times \cfrac{p_2 - 1}{p_2} \times ... \times \cfrac{p_m - 1}{p_m}$
只需求得 $N$ 的质因数 $p_i$ 即可，可以用到分解质因数的方法。
代码：

#include<iostream>
using namespace std;


int main()
{
   
    int n;
    cin >> n;
    while (n--)
    {
   
        int x;
        cin >> x;
        int res = x;
        for (int i = 2; i <= x / i; i++)
        {
   
        	// 分解质因数
            if (x % i == 0)
            {
   
                res = res / i * (i - 1);
                while (x % i == 0) x /= i;
            }
        }
        // 最后的质因数
        if (x > 1) res = res / x * (x - 1);
        
        cout << res << endl;
    }
    return 0;
}

筛法求欧拉函数

思路：
在用线性筛法求质因数的过程中，可以同时求出很多东西，比如某个数的欧拉函数。 $\sim N$ 中与 $N$ 互质的数的个数即为 $N$ 的欧拉函数，记作 $\phi(N)$ 。

若 $N$ 为质数，则 $\phi(N) = N-1$
若 $N$ 不为质数， $N$ 只会被最小的质因数给筛掉。
记 $p_j$ 为 $N$ 的质因子，枚举 $\sim N$ ，记作 $i$ 。
- 若 $i \mod p_j = 0$ ，则 $p_j$ 为 $p_j \times i$ 的最小质因子，根据欧拉函数的计算公式: $\phi(p_j \times i) = (p_j \times i) \times \cfrac{p_1 - 1}{p_1} \times \cfrac{p_2 - 1}{p_2} \times ... \times \cfrac{p_k - 1}{p_k}$ $p_1 \sim p_k$ 均为 $i$ 的质因子， $p_j \in \{p_1,...,p_k\}$ 。
  观察 $\times\cfrac{p_1 - 1}{p_1} \times \cfrac{p_2 - 1}{p_2} \times ... \times \cfrac{p_k - 1}{p_k}$ ，可以用 $\phi(i)$ 表示，则 $\phi(p_j \times i) = p_j \times \phi(i)$
- $\mod p_j \ne 0$ ， $p_j$ 小于 $i$ 的最小质因子，则 $p_j$ 是 $p_j \times i$ 的最小质因子
  $\begin{aligned} ϕ (p_{j} \times i) & = (p_{j} \times i) \times \frac{p_{1} - 1}{p_{1}} \times . . . \times \frac{p_{j} - 1}{p_{j}} \times . . . \times \frac{p_{k} - 1}{p_{k}} \\ = (i \times \frac{p_{1} - 1}{p_{1}} \times \frac{p_{2} - 1}{p_{2}} \times . . . \times \frac{p_{k} - 1}{p_{k}}) \times (p_{j} \times \frac{p_{j} - 1}{p_{j}}) \\ = ϕ (i) \times (p_{j} - 1) \end{aligned}$
  这样，便能遍历一次，求出 $\sim N$ 内所有欧拉函数之和，这就是筛法求欧拉函数。

欧拉定理，若 $a$ 与 $n$ 互质，则 $a^{\phi(n)} \equiv 1\:\:(mod \:\:n)$
证明：
$\sim n$ 中与 $n$ 互质的数为
$a_1,a_2,a_3...,a_{\phi(n)}$
每个数 $\times a$ ，得
$aa_1,aa_2,aa_3,...,aa_{\phi(n)}$
每个数都与 $n$ 互质，在模 $n$ 的概念下，两组数可看作相同的，则有下式：

\begin{aligned} a_{1} a_{2} a_{3} . . . a_{ϕ (n)} & \equiv a a_{1} a a_{2} a a_{3} . . . a a_{ϕ (n)} (m o d n) \\ a^{ϕ (n)} & \equiv 1 (m o d n) \end{aligned}

$\begin{aligned} a_1a_2a_3...a_{\phi(n)} &\equiv aa_1aa_2aa_3...aa_{\phi(n)} \:\:(mod \:\:n) \\ a^{\phi(n)} &\equiv 1 \:\:(mod \:\:n) \end{aligned}$

a_{1} a_{2} a_{3} ... a_{ϕ (n)} a^{ϕ (n)} \equiv a a_{1} a a_{2} a a_{3} ... a a_{ϕ (n)} (m o d n) \equiv 1 (m o d n)

特例： 费马定理
若 $p$ 为质数，则 $a^ {\phi(p)} \equiv 1 \:\:(mod \:\:p)$ ，即 $a^ {p-1} \equiv 1 \:\:(mod \:\:p)$

代码：

#include<iostream>
using namespace std;

typedef long long ll;

const int N = 1000010;
int primes[N], phi[N], cnt;
bool st[N];

ll get_eulers(int n)
{
   
    ll res = 0;
    phi[1] = 1;
    
    for (int i = 2; i <= n; i++)
    {
   
        if (!st[i]) primes[cnt++] = i, phi[i] = i - 1;
        for (int j = 0; primes[j] <= n / i; j++)
        {
   
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
   
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    
    for (int i = 1; i <= n; i++) res += phi[i];
    
    return res;
}

int main()
{
   
    int n;
    cin >> n;
    cout << get_eulers(n) << endl;
    return 0;
}

快速幂

思路：
快速幂的思想是将指数 $k$ 看作二进制数之和这样便可以在 $O (l o g k)$ 的复杂度中求得结果。则推出下式

\begin{aligned} k & = 2^{i} + . . . + 2^{j} + . . . + 2^{\log k} \\ a^{k} & = a^{2^{i}} . . . a^{2^{j}} . . . a^{2^{\log k}} \end{aligned}

$\begin{aligned} k &= 2^i+...+2^j+...+2^{\log k} \\ a^k &= a^{2^i}...a^{2^j}...a^{2^{\log k}} \end{aligned}$

k a^{k} = 2^{i} + ... + 2^{j} + ... + 2^{l o g k} = a^{2^{i}} ... a^{2^{j}} ... a^{2^{l o g k}}

又知

\begin{aligned} a^{2^{0}} & = a \\ a^{2^{1}} & = a^{2^{0} \times 2} = (a^{2^{0}})^{2} \\ . . . \\ a^{2^{\log k}} & = a^{2^{(\log k) - 1} \times 2} = (a^{2^{(\log k) - 1}})^{2} \end{aligned}

若

k

第

i

位为

1

，则结果

\times a^{2^i} \: mod \:p

，同时

k

右移一位，底数平方得

a^{2^{i+1}}

，

\: mod \:p

，继续计算下一位。
代码

#include<iostream>
using namespace std;

typedef long long ll;

int q_pow(int a, int b, int p)
{
   
    int res = 1;
    while (b)
    {
   
        if (b & 1) res = (ll) res * a % p;
        b >>= 1;
        a = (ll) a * a % p;
    }
    return res;
}

int main()
{
   
    int n;
    scanf("%d", &n);
    
    while (n--)
    {
   
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%d\n", q_pow(a, b, p));
    }
    
    return 0;
}

快速幂求逆元

思路：
若整数 $b$ ， $m$ 互质，并且对于任意的整数 $a$ ，如果满足 $b ∣ a$ ，则存在一个整数 $x$ ，使得 $\equiv a×x(mod \:m)$ ，则称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b^{-1}(mod \:m)$ 。

\begin{aligned} a / b & \equiv a \times x (m o d m) \\ a / b \times b & \equiv a \times b \times x (m o d m) \\ b \times x & \equiv 1 (m o d m) \end{aligned}

$\begin{aligned} a/b &\equiv a×x \:(mod \:m) \\ a/b \times b &\equiv a \times b \times x\:(mod \:m) \\ b \times x &\equiv1\:(mod \:m) \\ \end{aligned}$

a / b a / b \times b b \times x \equiv a \times x (m o d m) \equiv a \times b \times x (m o d m) \equiv 1 (m o d m)

又根据费马定理，

b^ {m-1} \equiv 1 \:\:(mod \:\:m)

，则

\times x = b^ {m-1}

，

x = b^ {m-2}

，若整数

b

，

m

互质，则存在

b

的乘法逆元。

代码

#include<iostream>
using namespace std;

typedef long long ll;

int q_pow(int a, int b, int p)
{
   
    int res = 1;
    while (b)
    {
   
        if (b & 1) res = (ll) res * a % p;
        b >>= 1;
        a = (ll) a * a % p;
    }
    return res;
}

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

int main()
{
   
    int n;
    scanf("%d", &n);
    
    while (n--)
    {
   
        int a, p;
        scanf("%d%d", &a, &p);
        int res = q_pow(a, p - 2, p);
        // 最大公因数为1，互质
        // if (a % p) 也可，
        if (gcd(a, p) == 1)printf("%d\n", res);
        else puts("impossible");
    }
    
    return 0;
}

扩展欧几里得算法

思路：
裴蜀定理: 对任何整数 $a$ 、 $b$ ，存在整数 $x$ 、 $y$ ，使得 $a x + b y = (a, b)$ ， $(a, b)$ 表示 $a$ 、 $b$ 的最大公因数，令 $d = (a, b)$ 。
若 $b = 0$ ，则 $d = a$ ， $x = 1$ ， $y = 0$
由数学定理知， $\: mod \: b)$ 。 $a$ 、 $b$ 交换顺序后，则有
$\: mod \: b)x+by=d \\ (a \: mod \: b) = a - \lfloor \cfrac{a}{b} \rfloor b \\ (a - \lfloor \cfrac{a}{b} \rfloor b)x+by = d \\ ax + (y - \lfloor \cfrac{a}{b} \rfloor x)b = d$
根据公式看到，与 $b$ 位置相同的参数的系数对应的为 $y$ 。

代码：

#include<iostream>
using namespace std;

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

int exgcd(int a, int b, int &x, int &y)
{
   
    if (!b)
    {
   
        x = 1, y = 0;
        return a;
    }
    
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
   
    int n;
    scanf("%d", &n);
    while (n--)
    {
   
        int a, b, x, y;
        scanf("%d%d", &a, &b);
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
    return 0;
}

线性同余方程

思路：
$\because a x \equiv b(\mod m)，\exist y \in Z$ ,使得： $a x - m y = b$ 。令 $y = - y$ ,则 $a x + m y = b$ ，令 $d = (a, m)$ ，并且 $d ∣ b$ 。
用拓展欧几里得算法求解， $a x + m y = d$ ， $x$ 、 $y$ 扩大 $\cfrac{b}{d}$ 倍，即可化为 $a x + m y = b$ 。
输出答案必须在 $in t$ 范围之内，计算出来的 $x$ 可能超过限制，又
$\mod m = (a * (x \mod m)) \mod m$
保险起见，最后的 $\mod m$ 。
代码：

#include<iostream>
using namespace std;

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

int exgcd(int a, int b, int &x, int &y)
{
   
    if (!b)
    {
   
        x = 1, y = 0;
        return a;
    }
    
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
   
    int n;
    scanf("%d", &n);
    while (n--)
    {
   
        int a, b, m, x, y;
        scanf("%d%d%d", &a, &b, &m);
        int d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else printf("%d\n", (long long)b / d * x % m);
    }
    return 0;
}

转载：https://blog.csdn.net/weixin_51624761/article/details/128532782

查看评论

小言_互联网的博客

小言_互联网的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章