C/C++教程

[AcWing 197] 阶乘分解

本文主要是介绍[AcWing 197] 阶乘分解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

image


点击查看代码
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n;
vector<int> primes;
bool st[N];

void get_primes(int x)
{
    for (int i = 2; i <= x; i ++) {
        if (!st[i])
            primes.push_back(i);
        for (auto p : primes) {
            if (p * i > x)
                break;
            st[p * i] = true;
            if (i % p == 0)
                break;
        }
    }
}

void solve()
{
    cin >> n;
    get_primes(n);
    for (auto p : primes) {
        int s = 0;
        for (int i = n; i; i /= p)
            s += i / p;
        cout << p << ' ' << s << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

  1. 首先用线性筛法筛出所有小于等于 \(n\) 的质数,对于一个质数 \(p\),可以求出在 \(n!\) 中出现多少次:
    ① \(p\) 的倍数在 \(1\) ~ \(n\) 中出现的次数,即 \(\frac{n}{p}\)
    ② \(p^2\) 的倍数在 \(1\) ~ \(n\) 中出现的次数,即 \(\frac{n}{p^2}\)
    \(\cdots\)
    ③ \(p^k\) 的倍数在 \(1\) ~ \(n\) 中出现的次数,即 \(\frac{n}{p^k}\)
    由于求的是次方数,\(p\) 的倍数是 \(1\) 次方,\(p^2\) 的倍数是 \(2\) 次方,\(\cdots\),\(p^k\) 的倍数是 \(k\) 次方,对于 \(p^2\),在计算 \(p\) 的倍数时会加 \(1\) 次(\(p^2 = p \cdot p\)),在计算 \(p^2\) 的倍数时会加 \(1\) 次(\(p^2 = 1 \cdot p^2\)),总共加了 \(2\) 次,刚好是次方数,对于 \(p^3\),在计算 \(p\) 的倍数时会加 \(1\) 次(\(p^3 = p^2 \cdot p\)),在计算 \(p^2\) 的倍数时会加 \(1\) 次(\(p^2 = p \cdot p^2\)),在计算 \(p^3\) 的倍数时会加 \(1\) 次(\(p^3 = 1 \cdot p^3\)),总共加了 \(3\) 次,刚好是次方数
    即对于 \(p^k\),会在 \(p, p^2, \cdots ,p^k\) 各加 \(1\) 次,总共 \(k\) 次,刚好是次方数
    故 \(p\) 的次方数为 $s = \frac{n}{p} + \frac{n}{p^2} + \cdots + \frac{n}{p^k} $
  2. 任意质数必定至少出现一次,因为筛出来的是满足小于等于 \(n\) 的质数
这篇关于[AcWing 197] 阶乘分解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!