线上OJ:
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1947
核心思想:
本题的意思是 在所有的
S
i
Si
Si 中,找一个
S
i
t
Si^t
Sit 最早能被
m
1
m
2
m1^{m2}
m1m2 整除。
上述若能整除,则说明:
1、
m
1
m1
m1 的质因数肯定是
S
i
Si
Si 质因数的子集 (换句话说,m1 的质因数都是 Si 的因数。如果
m
1
m1
m1 中某个质因数不能整数
S
i
Si
Si,则整个
S
i
t
Si^t
Sit 不可能被
m
1
m
2
m1^{m2}
m1m2 整除)
2、若
m
1
m1
m1 的质因数本身是多次幂(比如
m
1
m1
m1 为40,则
m
1
=
2
∗
2
∗
2
∗
5
=
2
3
∗
5
m1 = 2*2*2*5 = 2^3*5
m1=2∗2∗2∗5=23∗5,即质因数2的幂次为3,质因数5的幂次为1)。若此时的 m2 是2,则
m
1
m
2
=
(
2
3
∗
5
1
)
2
=
(
2
3
∗
2
)
∗
(
5
1
∗
2
)
=
2
6
∗
5
2
m1^{m2} = (2^3*5^1)^2 = (2^{3*2})*(5^{1*2})=2^6*5^2
m1m2=(23∗51)2=(23∗2)∗(51∗2)=26∗52。
如果此时 S i Si Si 的质因数中,2有6个,5有2个,则 1 秒后到达 S i Si Si 即可直接整除 m 1 m 2 m1^{m2} m1m2
如果此时 Si 的质因数中,2有3个,5有1个,则2个周期后可整除 m 1 m 2 m1^{m2} m1m2
如果此时 Si 的质因数中,2有2个,5有1个,则3个周期后才能整除 m 1 m 2 m1^{m2} m1m2
故, S i Si Si 的分裂周期为 S i Si Si 的质因数中分裂周期最多的那个
关键步骤:
1、先计算
m
1
m1
m1 的质因数,存储到数组
p
[
i
]
p[i]
p[i] 中;用
c
[
i
]
c[i]
c[i] 记录质因数
p
[
i
]
p[i]
p[i] 的个数。
2、如果是质数,要单独考虑
3、如果m1为1,则无需计算,直接输出
4、在读入每个
S
i
Si
Si 时按以下步骤进行:
a. 检查m1的每一个质因数是否都是 Si 的因数,如果有一个不是,则Si不可能被除尽
b. 检查每一个质因数在 Si 中出现的次数
c. 求出每一个质因数需经过几个周期方能被
m
1
m1
m1 中对应的幂次整除
举例: S i Si Si 为800,m1为40,m2 是2。则 S i = 2 5 ∗ 5 2 , m 1 m 2 = 2 6 ∗ 5 2 Si=2^5*5^2,m1^{m2} =2^6*5^2 Si=25∗52,m1m2=26∗52。细胞 Si 经过一个周期变为 2 5 ∗ 5 2 2^5*5^2 25∗52,无法被 2 6 ∗ 5 2 2^6*5^2 26∗52 整除,经过两个周期变为 2 10 ∗ 5 4 2^{10}*5^4 210∗54,可以被 2 6 ∗ 5 2 2^6*5^2 26∗52 整除。所以 Si=800的需要2个周期。
d. 找出 Si 的所有质因数中分裂周期最多的那个
5、所有的 Si 都读完后,找出分裂周期最小的数值,就是本题的答案。
题解代码:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 30005;
int n, m1, m2, s, ans, maxn;
// p[i]记录m1的第i个质因数,c[i]表示m1的第i个质因数的个数。比如12=2*2*3,所以p[1]=2,c[1]=2,p[2]=3,c[2]=1
int p[N], c[N], cnt = 0; // cnt记录m1的质因数的个数。比如 12的质因数是2和3,则cnt=2
bool isprime = true; // m1是否为质数
int main()
{
scanf("%d %d %d", &n, &m1, &m2);
if(m1 == 1) // 如果m1为1,说明就1个试管,直接放即可
{
printf("0\n");
return 0;
}
int x = m1;
for(int i = 2; (i*i <= m1) && x; i++) // 求出m1的所有质因数,以及每个质因数的个数
{
if( x % i == 0 ) // 如果存在i能整除m1
{
isprime = false; // 如果找到一个质因数,则m1不是质数
p[++cnt] = i; // 将质因数 i 存到p数组里,p数组从p[1]开始
}
while( x % i == 0 )
{
c[cnt]++; // 记录m1的质因数 i 的个数
x /= i;
}
}
if(isprime) // 如果是质数,则上述for循环无法找到质因数。
{
p[++cnt] = m1; // 质数的质因数只有自己
c[cnt] = 1;
}
ans = INF;
while(n--) // 读入n个数,逐次判断
{
maxn = -INF; // 每一轮开始前,先初始化。maxn 记载读入s需要分裂的周期
bool flag = true;
scanf("%d", &s);
for(int i = 1; i <= cnt && s; i++) // 检查m1的每一个质因数是否都是s的因数
{
int a = 0;
if(s % p[i]) // 如果m1的质因数p[i]不是s的因数,则s不可能被m1^m2除尽
{
flag = false;
break;
}
while(s % p[i] == 0) // 如果能除尽,则统计s内有多少个p[i]
{
a++;
s /= p[i];
}
maxn = max(maxn, (c[i]*m2 + a - 1)/a); // s的分裂周期为s的质因数中分裂周期最多的那个。举例:质因数2需要分裂5次能满足,质因数3需要分裂2次就能满足,则s的分裂周期为5
}
if(!flag) continue;
ans = min(ans, maxn); // 在所有的s种,找一个分裂周期最小的
}
if(ans == INF) printf("-1\n");
else printf("%d\n", ans);
return 0;
}