分解质因数

分解质因数

方法

分解质因数就是把一个数,用自己所有的质因数的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;
}