哈哈哈哈,我胡汉三又回来了。
话不多说,题目如下:
图片说明
题目的意思我就不再多说了,对于解法,目前本人看到的大概可以归结为两种,用和不用二分法的。个人觉得不用二分法的更简单,本着先难后易的原则,我们先来介绍一下用二分法怎么解。
对于二分法,我们要先明确将那个量进行二分,然后再确定该变量的左右范围。对于本题,我们将我们要求的值,也就是n进行二分,接下来,我来介绍一下具体的思路:
首先,我们将输入的p进行质因数分解,为什么?因为满足条件的n!可能十分大,如果不对它进行质因数分解的话,那你就得算出n!,被T风险不说,还可能爆掉。
来看这个代码就是进行质因数分解的,我们的目的是统计出它的质因数(用primer数组)和对应的质因数的个数(用num数组),如:primer[1]表示的是第一个质因数,num[1]表示第一个质因数的个数。其实可以用容器的,但考虑到本博文主要针对同为萌新的我们,还是算了吧

for(int i=2;i*i<=p;i++){  //对质因数进行分解 
        if(p%i==0){
            primer[++k]=i;  //注意这里是++k 
            while(p%i==0){
                num[k]++;
                p/=i;
            }
        }
}
if(p>1)  primer[++k]=p,num[k]++;

这里,利用了类似埃式筛的想法,从2开始,建议这个方法可以记住,如果遇到了当前的i式p的因数,那么就将它存入primer数组里,然后用一个while循环计算它的个数,同时更新p。这里可能有些同学就看不太懂了,说那他
它进去的i可能不是质数。其实,它存进去的i一定是质数,因为我有个while循环来更新p,我举个例子,我们是从2开始的,而且只有p不能被2整除后才能跳出while循环,那你说,后面4,6,8之类的还能进入if语句里吗?同样,3是素数,它被存入primer数组后3的倍数就不能再进入if语句了。其实,这就是一个埃式筛法的思想,我也是今天才真正学会这么用。所以说建议可以记住这个写法。然后就是要注意这个k是++k,不是k++,两者的区别我就不解释了,我想说的是我们的数组是从下标为1开始的,这个k最后就记录了p里面有几个质因数。然后,出了for循环后,再进行一个判断,假如此时的p没有被分解为1,那说明p本身就是一个素数,那就要将p存入primer数组

int l=1,r=1e9,ans;
    while(l<=r){
        int mid=(l+r)/2;
        if(judge(mid)){  //如果这时候的mid满足题意,但我们要求的是最小的,所以将区间移到左边,即将右限左移,mid-1 
            r=mid-1;
            ans=mid;
        }
        else  l=mid+1;
    }

既然质因数分解好后,我们接下来就进行二分,首先,做区间我们设为1,右区间设为1e9(因为你的值最大就是这么多,其实也不必这么大)。我们从这个区间里找出一个mid,再对mid进行判断是否为满足条件的n,如果满足,那么我们就往左边继续找,同时记下此时的mid。至于为什么往左边?因为我们是找最小的n,如果此时的mid是满足的,但我们不知道它是否为最小的,所以我们要将查找的范围往左边移,即将r往左移。否则,将l往右移,这里我再来提醒一个小技巧,对于mid的求法,我们分为mid=(l+r)/2,mid=l+(r-l)/2,mid=(l+r)>>1,这三种写法,个人建议尽量选择后两种,因为第一种可能再某些情况下会超过int范围,建议习惯后两种写法。
我们再来看看judge函数:

bool judge(int x){  //判断函数
    for(int i=1;i<=k;i++){
        int n=x,num_primer=0;
        while(n){
            num_primer+=n/primer[i];
            n/=primer[i];
        }
        if(num_primer<num[i])  return false;
    }
    return true;
}

我们对primer数组进行遍历,再对每个质因数进行判断,在这个传进来要进行判断的值mid的情况下,它的阶乘是否可以满足条件。我们要计算n!里面的当前primer[i]元素下的个数,我们用num_primer表示,就是那个while循环来完成,举个例子,当前检验mid=8时,假如此时的primer[i]=2,对于8!我们看到1-8里面有质因数2的倍数的数字为2,4,6,8,就是4个,然后将8除以这个质因数2,相当于对在上一个条件下的2,4,6,8除以2,然后1-4里面有2个2的倍数,即2,4。然后4除以2,就是1-2里面,里面有一个2的倍数,一共加起来就是4+2+1=7个2,其他也是这样类推,(这个可以好好体会)。所以我们将n=x,放到了循环里面,因为你检验的每个质因数都是独立的。每个循环用的mid要一样。我们求到此情况下的primer[i]的个数,然后将num_primer与我们对p进行质因数分解得到的num[i]进行比较,如果num_primer<num[i],那么说明这个mid不能满足,直接返回false,如果所有的primer元素都满足,则最后返回true。
接下来,就是总的代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int p,num[maxn],primer[maxn],k;
bool judge(int x){  //判断函数
    for(int i=1;i<=k;i++){
        int n=x,num_primer=0;
        while(n){
            num_primer+=n/primer[i];
            n/=primer[i];
        }
        if(num_primer<num[i])  return false;
    }
    return true;
}
void solve(){
    k=0;
    for(int i=2;i*i<=p;i++){  //对质因数进行分解
        if(p%i==0){
            primer[++k]=i;  //注意这里是++k
            while(p%i==0){
                num[k]++;
                p/=i;
            }
        }
    }
    if(p>1)  primer[++k]=p,num[k]++;
    int l=1,r=1e9,ans;
    while(l<=r){
        int mid=(l+r)/2;
        if(judge(mid)){  //如果这时候的mid满足题意,但我们要求的是最小的,所以将区间移到左边,即将右限左移,mid-1
            r=mid-1;
            ans=mid;
        }
        else  l=mid+1;
    }
    memset(num,0,sizeof(num));  //记住,因为这是多组测试,所以要将num数组置为0,以便不会影响下次
    cout<<ans<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>p;
        solve();
    }
    return 0;
}

写了好久了,还要接着写吗。。。
接下来,我们来介绍一下不用二分法的做法,其实如果你上面的学会了,那么下面的就很好理解了。
我们先将p是1和质数的情况进行考虑,如果p是质数和1,那么直接输出p就行,这个你可以打表看看。接下来,我们就看看第三种情况:

 for(int i=2;;i++){
       if(gcd(i,p)!=1){
            p/=gcd(i,p);
             if(p==1){
              cout<<i<<endl;
               break;
            }
             if(i<p&&isprimer(p)){
                cout<<p<<endl;
                 break;
           }
      }
}

我们从2开始,找出此时的i与p的最大公因数,同时更新此时的p,如果到了某个i时p为1,那么输出i即可,或者某一个i时还小于p,并且此时p为素数,那么说明只有i到达p时,p才能为1输出,那么这种情况可以直接输出p即可。
代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool isprimer(int n){
    if(n==1)  return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)  return false;
    }
    return true;
}
int gcd(int a,int b){
    if(b==0)  return a;
    else  return gcd(b,a%b);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int p;
        cin>>p;
        if(p==1)  cout<<p<<endl;
        else if(isprimer(p))  cout<<p<<endl;  //素数
        else{   //不是素数
            for(int i=2;;i++){
                if(gcd(i,p)!=1){
                    p/=gcd(i,p);
                    if(p==1){
                        cout<<i<<endl;
                        break;
                    }
                    if(i<p&&isprimer(p)){
                        cout<<p<<endl;
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

说明一下,因为最近主要在做学校的二分法专题,感觉还是得写一下二分的解法,所以趁周日写了这篇博文,(写了三个小时)。感觉还是挺花时间的。明天还要上网课,今晚还得预习,不然还想进行一个题型的总结,那就可能咕咕咕了。以后有时间吧,这几周有点耽误网课啊!好好学习吧。
有疑问下方留言,欢迎指正错误之处。