算数基本定理

每个大于1的正整数都可以被唯一分解为素数的成绩，在乘积中的素因子按照非降序排列

a = p1^a1 * p2^a2 * ... pn^an;
b = p1^b1 * p2^b2 * ... pn^bn;
gcd(a,b) = p1^min(a1,b1) * p2^min(a2,b2) * ... pn ^ min(an,bn);
lcm(a,b) = p1^max(a1,b1) * p2^max(a2,b2) * ... pn ^ max(an,bn);
max(gcd(a,b)) + min(gcd(a,b)) = a + b;
n!的素因子分解中素数p的幂为[n/p]+[n/p^2]+[n/p3]... p^t <= n
在因式分解中，2的因子的个数要大于5的因子的个数

题意：计算N!末尾的0的个数

分析：

显然分析是很重要的，计算末尾0的个数显然不科学，所以转化为计算2*5的个数，又有定理：在因式分解中，2的因子的个数要大于5的因子的个数，

则只要计算5的幂就好，用公式n!的素因子分解中素数p的幂为[n/p]+[n/p^2]+[n/p3]... 0（p^t <= n）

算数基本定理的应用

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

using namespace std;

typedef long long ll;

int main()

{

    int cas;

    cin >> cas;

    while(cas--)

    {

        ll n;

        cin >> n;

        ll five = 5;

        ll sum = 0;

        while(five < n)

        {

            sum += n/five;

            five *= 5;

        }

        cout << sum << endl;

    }

    return 0;

}

巴特西

算数基本定理 - nefu 118

算数基本定理

题意：计算N!末尾的0的个数

分析：

算数基本定理的应用

最新文章

热门文章