分解质因数

方法

分解质因数就是把一个数，用自己所有的质因数的ai次方的乘积表示出来，而且这种表示方式是唯一的，格式如下：

$ n={a_{1}}^{b1} * {a_{2}}^{b2} * {a_{3}}^{b3} * cdots * {a_{i}}^{bi} $

其中，a都为质数，切为递增。

分解的方法为依次枚举因数ai，然后看n%ai是否可以为0，若可以，则为其中的一个质因数，然后不停地n/=ai，直到n%ai不为零，n/=ai的次数也就是bi的数。因为每次的n/=ai把非质数都给筛掉了，所以不需要担心ai不为质数。

一定要记得从2开始枚举，枚举到n的开方就行。如果发现质因数为0，则n=n^1;

代码

1
2
3
4
5
6
7
8
9
10
11
Now=n;
for(int i=2;i<=sqrt(double(n))+1;i++)
if(!(Now%i))
{
    First[++all].Prime=i;
    while(!(Now%i))
    {
        Now/=i;
        First[all].Number++;
    }
}

一些结论

关于约数和因数的区别

约数和因数既有联系,又有区别,这主要表现在以下三个方面.

  1. 约数必须在整除的前提下才存在,而因数是从乘积的角度来提出的.如果数a与数b相乘的积是数c,a与b都是c的因数.
  2. 约数只能对在整数范围内而言,而因数就不限于整数的范围.
    例如：6×8＝48.既可以说6和8都是48的因数,也可以说6和8都是48的约数.
    又如：0.9×8＝7.2.虽然可以说0.9和8都是7.2的因数,却不能说0.9和8是7.2的约数.
    从这一点来看,一个数的因数有可能大于它本身,而约数不能大于这个数的本身.
  3. 对于一个整数,凡能整除它的数,都是这个整数的约数.
    例如：1、2、4、8、16都能整除16,因此,1、2、4、8、16也都是16的约数.而当一个数被分解成两个或几个数相乘时,因数的个数就受到了限定.
    又如：2×8＝16.只能说2和8是16的因数,而不能说1、2、4、8、16都是的因数,因为1×2×4×8×16的结果,并不等于16.

因数个数

对于分解质因数:

$n = {a_{1}}^{b1} * {a_{2}}^{b2} * {a_{3}}^{b3} * \cdots * {a_{i}}^{bi}$

n的所有因数的个数为:

$all=(b1+1)* (b2+1)* (b3+1)* (bn+1)$

正约数之和

对于分解质因数:

$n={a_{1}}^{b1}* {a_{2}}^{b2} *{a_{3}}^{b3} *\cdots * {a_{i}}^{bi}$

n的正约数之和为:

$all=(1+{a_{1}}^{1} +{a_{1}}^{2} +\cdots +{a_{1}}^{b1}) *(1+{a_{2}}^{1}+ {a_{2}}^{2}+ \cdots+ {a_{2}}^{b2}) *\cdots\cdots * (1+{a_{i}}^{1}+ {a_{i}}^{2}+ \cdots +{a_{i}}^{bi})$

n!分解质因数后因子n的个数

证明过程：
这个网上一搜一大把，我只把核心的东西写出来：

  • m!=1*2*3*……*(m-2)*(m-1)*m
  • m!=(n*2n*3n*……*kn)*ohter
  • m!=n^k*(1*2*……*k)*other
  • m!=n^k*k!*other

因为kn<=m 而k肯定是最大值所以k=m/n;
从这个表达式中可以提取出k个n;
然后按照相同的方法循环下去可以求出k!中因子n的个数。

比如我们举个例子吧：

9的阶乘：1*2*3*4*5*6*7*8*9，求因子2的个数：

!9=1*(2)*3*(2*2)*5*6*7*(2*2*2*2)*9

然后求出k=8/2=4，m=9/2=4 所以就已经有了4个2。
然后求出k=4/2=2，m=4/2=2 所以就已经有了6个2。
然后求出k=2/2=1，m=2/2=1 所以就已经有了7个2。
然后求出k=1/2=0，m=1/2=0 m=0结束循环，一共用7个2。

代码：

1
2
3
4
5
6
7
8
9
10
void GetNumber(int n)
{
    Sum=false;
    while(m)
    {
        Sum+=m/n;
        m=m/n;
    }
    cout<<Sum<<endl;
}

NOIP2009 细胞问题

题目描述：

  • Hanks 博士是 BT (Bio-Tech，生物技术) 领域的知名专家。现在，他正在为一个细胞实 验做准备工作：培养细胞样本。
  • Hanks 博士手里现在有 N 种细胞，编号从 1~N，一个第 i 种细胞经过 1 秒钟可以分裂为Si 个同种细胞（Si 为正整数）。
  • 现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入 M 个试管，形成 M 份样本，用于实验。
  • M 总可以表示为 m1 的 m2 次方，即 M = m1^m2 ，其中 m1，m2均为基本数据类型可以存储的正整数。注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4个细胞，
  • Hanks 博士可以把它们分入 2 个试管，每试管内 2 个，然后开始实验。但如果培养皿中有 5 个细胞，博士就无法将它们均分入 2 个试管。此时，博士就只能等待一段时间，让细胞们继 续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。
  • 为了能让实验尽早开始，Hanks 博士在选定一种细胞开始培养后，总是在得到的细胞“刚 好可以平均分入 M个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细 胞培养，可以使得实验的开始时间最早。

输入：

  1. 第一行有一个正整数 N，代表细胞种数。
  2. 第二行有两个正整数 m1，m2，以一个空格隔开， m1^m2 即表示试管的总数 M。
  3. 第三行有 N 个正整数，第 i 个数 Si 表示第 i 种细胞经过 1 秒钟可以分裂成同种细胞的个 数。

输出：

共一行，为一个整数，表示从开始培养细胞到实验能够开始所经过的 最少时间（单位为秒）。无解输出-1.

题解：

这道题也是非常简单呢。

首先你需要明白，m1^m2是非常大的，但是你要怎么办呢？我们只需要对m1进行质因数分解就行了，然后数量就是m1质因子的数量*m2就行，因为m1经过m2次方之后，质因子是不变的，变得是数量，也就是:

$n^m = ({a_{1}}^{b1} * {a_{2}}^{b2} * {a_{3}}^{b3} * \cdots * {a_{i}}^{bi}) ^m $

$n^m = {a_{1}}^{b1m} * {a_{2}} ^ {b2m} * {a_{3}} ^ {b3m} * \cdots * {a_{i}} ^ {bim} $

所以也是避免了高精度的计算……

然后我们对于其他每个细胞的分裂数量都进行质因数分解，然后比对，如果m1有的细胞没有，那么这个细胞永远没有办法满足条件。如果所有的质因数都有的话，那么分裂需要的时间就是所有质因数的数量，也就是m1^m2的bi的数量除以细胞分裂数的质因数的数量bi，向上取整后的最大值。这个最大值就是细胞需要分裂的时间，然后找到所有细胞分裂时间中最小的输出就行了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
struct Prime_number
{
    int Prime;
    int Number;
}First[20000];
int n,m1,m2,a[20000],Maxx,ans=2123456789;
int Second[40000],all,Top,Now;
bool Flag=false;
inline int Read()
{
    int F=true;
    int This=false;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This\*F;
}
int main()
{
    n=Read(); m1=Read(); m2=Read(); Now=m1;
    for(int i=1;i<=n;i++) a[i]=Read();
    for(int i=2;i<=sqrt(double(m1))+1;i++)
    if(!(Now%i))
    {
        First[++all].Prime=i;
        while(!(Now%i))
        {
            Now/=i;
            First[all].Number++;
        }
        First[all].Number\*=m2;
        Top=i;
    }
    if(!all&&m1!=1)
    {
        First[++all].Prime=m1;
        First[all].Number=m2;
        Top=m1;
    }
    for(int i=1;i<=n;i++)
    {
        Now=a[i]; Flag=false; Maxx=false;
        memset(Second,false,sizeof(Second));
        for(int j=2;j<=min(int(sqrt(double(a[i]))+1),Top);j++)
        while(!(Now%j))
        {
            Now/=j;
            Second[j]++;
        }
        for(int j=1;j<=all;j++)
        {
            if(!Second[First[j].Prime])
            {
                Flag=true;
                break;
            }
            else
            {
                if(First[j].Number%Second[First[j].Prime])
                Maxx=max(Maxx,First[j].Number/Second[First[j].Prime]+1);
                else Maxx=max(Maxx,First[j].Number/Second[First[j].Prime]);
            }
        }
        if(!Flag) ans=min(Maxx,ans);
    }
    if(ans==2123456789) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

数学游戏

题目描述:

  • 小x最近迷上了一款数学游戏，游戏的规则是这样的：给定一个整数N，从1..N这N个整数中，任意选取若干个整数，使得选取的数的乘积是一个完全平方数。(一个数如果是另一个整数的完全平方，那么我们就称这个数为完全平方数，也叫做平方数。例如：1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529…)

  • 完全平方数的选取有很多种，现在我们只在乎这个完全平方数的最大值。这个最大值会很大，为了避免高精度，我们只需要知道最大值对1000000007去余数的值。

输入：

一个正整数N

输出：

一个正整数，最大得分对1000000007的模值。

题解：

这道题其实就是上面的对于!m的因数n的个数。首先我们明白，对于一个平方来说，其实就是找到所有质因子的偶数数量的乘积，因为对于一个数 x=n*n*n*m*m，来说，选择其中的一些来构成一个平方数的话，一定是选择每一个质因数的偶数个，比如n*n*m*m，这样的话就可以化成平方的形式:(n*n)*(n*m)，也就是n*m的二次方。

这样，我们就只需要把m以内的所有质数求出来，然后来求出!n的质因数的个数，然后取最大的偶数值，利用快速幂乘起来就行了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cctype>
using namespace std;
#define Mod 1000000007
long long n,m,Prime[2000000],This;
long long Total,Num,ans,Now;
bool vis[4000000];
void GetNumber(int x)
{
    Now=n;
    Num=false;
    while(Now)
    {
        Num+=Now/x;
        Now=Now/x;
    }
}
void Fast_Power(int x)
{
    This=x;
    while(Num)
    {
        if(Num&true) ans=ans\*This%Mod;
        Num>>=true;
        This=This\*This%Mod;
    }
}
int main()
{
    cin>>n;
    ans=true;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) Prime[++Total]=i;
        for(int j=i;j<=n;j+=i) vis[j]=1;
    }
    for(int i=1;i<=Total;i++)
    {
        GetNumber(Prime[i]);
        if(Num&true) Num--;
        Fast_Power(Prime[i]);
    }
    cout<<ans<<endl;
    return 0;
}