Light OJ Trailing Zeroes (I) (唯一分解定理)

唯一分解定理

一个数n肯定能被分解成 n=q1^a1* q2^a2*q3^a3…*qn^an
1、质数:对于质数而言,其因子只有1和其本身。
2、合数:一个合数可以分解为一个合数和一个质数,质数不可再分解,而合数还可以再分解下去。因此一个数就会变成多个(质数的n次方)的乘积
例如36可分解为2^2*3^2

所以唯一质数分解定理有两个应用

1、求一个数因子的个数
假设一个数因子个数为p
p=(1+a1)(1+a2)…(1+an)
2、求所有因子之和
公式(乘积):(q1^0+q1^1+q1^2…q1^a1)(q2^0+q2^1+q2^2…q2^a2)…x(qn^0+qn^1+qn^2…qn^an)

补充:对n!的质因分解

比如对8!进行质因分解,以2为例

8!= 1·2·3·4·5·6·7·8

2的指数为8/2 + 8/2/2 +8/2/2/2

原题代码:

#include <bits/stdc++.h>
using namespace std;
long long prime[1000010],p[1000010],cnt;
void eulor(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!p[i])
        {prime[++cnt]=i;}
        for(int j=1;j<=cnt;j++)
        {
            if(i*prime[j]>n)
            {break;}
            p[i*prime[j]]=1;
            if(i%prime[j]==0)
            {break;}
        }
    }
}
int main()
{
    long long op=0;
    long long t,n;
    eulor(1000000);
    scanf("%lld",&t);
    while(t--)
    {
        op++;
        scanf("%lld",&n);
        long long l=sqrt(n);
        long long ans=1,kk=0;
        for(int i=1;prime[i]<=l;i++)
        {
            kk=0;
            while(n%prime[i]==0)
            {
                n/=prime[i];
                kk++;
            }
            ans*=(kk+1);
            if(n==1)
            {break;}
        }
        if(n!=1)
        {ans=(ans*2)-1;}
        if(n==1)
        {ans--;}
        printf("Case %lld: %lld\n",op,ans);
    }
    return 0;
} 

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注