2023-07-12 10:17:14
发布于：上海
#include <bits/stdc++.h>
using namespace std;
int n,m1,m2,ans = 150000;
int i,j;
int s[100005],f[100005];
bool p[300005];
int prime[501][3],size = 0;
int main(void)
{
memset(p,1,sizeof(p));
memset(f,0,sizeof(f));
scanf("%d%d%d",&n,&m1,&m2);
if (m1 == 1)
{
printf("0");
return 0;
}
for (i = 1; i <= n; i++)
scanf("%d",&s[i]);
int xx = floor(sqrt(m1));
for (i = 2; i <= xx; i++)
{
if (p[i])
{
if (m1 % i == 0)
{
prime[size][1] = i;
prime[size][2] = 1;
}
}
int tim = 2;
while (tim * i <= m1)
{
p[tim * i] = 0;
tim;
}
}
for (i = 1; i <= size; i++)
{
int num = prime[i][1];
while (m1 % (num * prime[i][1]) == 0)
{
num *= prime[i][1];
prime[i][2];
}
prime[i][2] *= m2;
}
if (size == 0)
{
prime[size][1] = m1;
prime[size][2] = m2;
}
for (i = 1; i <= n; i)
{
for (j = 1; j <= size; j)
{
if (s[i] % prime[j][1] != 0)
{
f[i] = 150000;
break;
}
int tim = 1;
long long num = prime[j][1];
while (s[i] % (num * prime[j][1]) == 0)
{
num *= prime[j][1];
tim++;
}
int an = (prime[j][2]-1) / tim + 1;
if (an > f[i]) f[i] = an;
}
}
for (i = 1; i <= n; i++)
if (ans > f[i]) ans=f[i];
if (ans == 150000) printf("-1");
else printf("%d",ans);
return 0;
}
全部评论 5
#include <bits/stdc++.h>
using namespace std;
int n,m1,m2,ans = 150000;
int i,j;
int s[10001],f[10001];
bool p[30001];
int prime[501][3],size = 0;
int main(void)
{
memset(p,1,sizeof(p));
memset(f,0,sizeof(f));
scanf("%d%d%d",&n,&m1,&m2);
if (m1 == 1)
{
printf("0");
return 0;
} // If the number of tubes is 1, the conditions are met directly 若试管数为1，直接符合条件
for (i = 1; i <= n; i++)
scanf("%d",&s[i]);
int xx = floor(sqrt(m1));
for (i = 2; i <= xx; i++)
{
// Quality finding factor 找质因数
if (p[i])
{
if (m1 % i == 0)
{
prime[size][1] = i;
prime[size][2] = 1;
}
}
int tim = 2;
while (tim * i <= m1)
{
p[tim * i] = 0;
tim;
}
}
for (i = 1; i <= size; i++) // Number of quality finding factors 找质因数个数
{
int num = prime[i][1];
while (m1 % (num * prime[i][1]) == 0)
{
num *= prime[i][1];
prime[i][2];
}
prime[i][2] *= m2;
}
if (size == 0) // If it is a prime number, the prime factor is itself 若为质数，质因数为本身
{
prime[size][1] = m1;
prime[size][2] = m2;
}
for (i = 1; i <= n; i)
{
for (j = 1; j <= size; j)
{
if (s[i] % prime[j][1] != 0) // If there is no certain factor, break directly
{
f[i] = 150000; // Maximum: 10000 * log 2 30000
break;
}
int tim = 1;
long long num = prime[j][1];
while (s[i] % (num * prime[j][1]) == 0)
{
num *= prime[j][1];
tim++;
}
int an = (prime[j][2]-1) / tim + 1; // Equivalent to ceil function
if (an > f[i]) f[i] = an;
}
}
for (i = 1; i <= n; i++)
if (ans > f[i]) ans=f[i];
if (ans == 150000) printf("-1");
else pri2026-05-31 来自 广东
0
有帮助，赞一个