一 题目描述

题目链接: link.

二 解题思路

整体分析：用到了欧拉筛＋整数分解。

一 手写分析

二 简要概括

①欧拉筛，筛出3000以内的素数，放在sum_prime数组中。
②大整数分解
③判断是否可以覆盖
④依次比较每个细胞所用时间t，选取最小值。

三 题解代码

// A code block
var foo = 'bar';

#include<bits/stdc++.h> 
using namespace std;
const int maxn=30000+10;
int n,i,j,m1,m2,minn=2147483647;
int prime[maxn]={0};  //30000以内所有的质数
bool flag=false,here;  //flag为所有细胞，here为单个细胞的判断
int pipe_prime[maxn];  //试管的质因数分解
int cell_prime[maxn];  //细胞的质因数分解
int sum_prime=0,cell,now;  //30000以内质数总数记为sum_prime
bool pr(int k)  //判断是否为素数，不予以注释
{
    int m;
    for(m=2;m<=floor(sqrt(k));m++)
    if(k%m==0)return false;
    return true;
}
int main()  //主程序开始
{
    cin>>n; cin>>m1>>m2;
    for(i=2;i<=maxn;i++)  //把30000以内的质因数枚举出来
    if(pr(i))
    {
        sum_prime++;
        prime[sum_prime]=i;
    }
    i=1; while(m1!=1)  //为m1质因数分解
    {
        if(m1%prime[i]==0)
        while(m1%prime[i]==0)  //除到没有为止
        {pipe_prime[i]+=m2; m1/=prime[i]; }
        i++;
    }
    for(i=1;i<=n;i++)
    {
        cin>>cell; j=1; now=0; here=true;  //初始化
        memset(cell_prime,0,sizeof(cell_prime));  //初始化，加头文件cstring
        while(j<=sum_prime)  //大于30000的质因子忽略，即在30000内质因数分解
        {
            if(cell%prime[j]==0)
            while(cell%prime[j]==0)
            {cell_prime[j]++; cell/=prime[j]; }
            j++;
        }
        for(j=1;j<=sum_prime;j++)
        {
            if(pipe_prime[j]!=0&&cell_prime[j]==0)here=false;  //如果细胞没有试管所拥有的质因子，该细胞不可用
            if(pipe_prime[j]!=0&&cell_prime[j]!=0)  //如果试管没有该质因子，不用做
            {
                if(pipe_prime[j]%cell_prime[j]==0)
                now=max(now,pipe_prime[j]/cell_prime[j]);
                else now=max(now,pipe_prime[j]/cell_prime[j]+1);  //记得要+1，整除时不用加
            }
        }
        if(here){flag=true; if(now<minn)minn=now;}  //如果该细胞可行，做个标志，替换
    }
    if(flag)cout<<minn<<endl;  //如果可行
    else cout<<-1<<endl;
    return 0;
}

四 每日共勉

天行健，君子以自强不息。