P1574 超级数

· · 题解

题意简述：

额，裸的一道模板题目学过反素数的伙伴们，肯定非常眼熟，没错，这就是求我们不大于 a_i 的最大反素数。

思路：

网上搜索反素数表，开个数组存下来，然后二分查一以下……

上述事情是不可能发生的，就算打表，作为新时代的好少年们肯定也必须自己写代码来记录下来打表。

首先，先跟大家说一下反素数的定义（其实和题目没什么大区别）：

然后，说一下反素数的性质：

  1. 一个反素数的质因子必然是从 2 开始连续的质数.

所以接下来我们需要求反素数！

求反素数：

1.暴力：

考虑直接暴力枚举以及的因数，时间复杂度约为 O(n^2 \log_2 n)。

#include <cstdio>
int yz(int t) {
    int ans=0;
    for(int i=1; i<=t; i++) {
        if(t%i==0) {
            ans++;
        }
    }
    return ans;
}
bool pd(int x) {
    int dz=yz(x);
    for(int i=1; i<=x-1; i++) {
        if(yz(i)>=dz) {
            return false;
        }
    }
    return true;
}
int main() {
    int n=0;
    scanf("%d",&n);
    for(int i=n; ; i--) {
        if(pd(i)==true) {
            printf("%d",i);
            break;
        }
    }
    return 0;
}

2.暴力优化：

还是考虑直接暴力枚举 x，但是我们可以通过优化枚举因数的时间复杂度来降低整个程序的时间复杂度，这种方法的时间复杂度约为 O(n \log_2 n \sqrt{t})。

#include <cstdio>
#include <cmath>
int yz(int t) {

    int ans=0;
    int mj=sqrt(t);
    for(int i=1; i<=mj; i++) {
        if(t%i==0) {
            ans+=2;
        }
    }
    if(mj*mj==t) {
        ans--;
    }
    return ans;
}
bool pd(int x) {
    int dz=yz(x);
    for(int i=1; i<=x-1; i++) {
        if(yz(i)>=dz) {
            return false;
        }
    }
    return true;
}
int main() {
    int n=0;
    scanf("%d",&n);
    for(int i=n; ; i--) {
        if(pd(i)==true) {
            printf("%d",i);
            break;
        }
    }
    return 0;
}

3.满分思路：

什么是反素数？

反素数就是区间内约数个数最多的那个数。根据题目要求，如果有多个满足，选取最小的一个。

如果我们要求的区间就是 [1,10]。

那么我们怎么求反素数呢？

如果我们设为 p 指数，k 为指数的话，那么如果一个数可以被分成如下形式：

x=\prod\limits_{i=1}^np_i^{k_i}

那么 x 的因数个数就是 \prod\limits_{i=1}^nk_{i}+1。

如果设 p_i 严格递增，并且 k_i=0 也算在内，则如果 k_x<k_y 并且 x<y，那么显然这个数不可能是反素数，因为交换 k_x 和 k_y 会更好。

所以当递增时是递减的，这个数才可能是反素数。

所以我们可以据此搜索。

素数表可以筛一波，也可以这样：

因为前 12 个素数的积 >2 \times 10^9，所以最多用到 12 个素数，手动打素数表即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long p[20]= {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
long long maxn=-1,ans=-1;
long long n=0;
void get(long long m,long long f,long long t,long long pr) {
    //f为当前质数的编号，当前指数<pr
//t为当前约数的个数， m表示当前可能成为最优解的数
    if(t>maxn || (t==maxn && m<ans)) { //更新最优解
        ans=m,maxn=t;
    }
    long long i=m,j=0;
    long long nt=0;
    while(j<pr) { //j表示的是当前正在搜索的指数
        j++;
        if(n/i<p[f]) { //若不满足条件就跳出循环（i表示的是当前的m）
            break;
        }
        nt=t*(j+1),i*=p[f];//更新新数以及它的因子个数。
        if(i<=n) { //若i（即当前的m）在区间[1,n]内就继续搜索。
            get(i,f+1,nt,j);
        }
    }
}
int main() {
    scanf("%lld",&n);
    get(1,1,1,30);
    printf("%lld",ans);
    return 0;
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int p[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}; //打表 
int n, tid[maxn];
ll now, res, val, Q[maxn], ans[maxn];
void dfs(int pos, ll sum, ll tot, int lst){ //搜索找反素数 
    for (ll i = 0, t = sum; i <= lst; i++, t *= p[pos]){
        if (pos < 16) //前16个素数还没有搜完 
          dfs(pos + 1, t, tot * (i + 1), i);
        if ((res >= t && val <= tot) || (res < t && val < tot))
          res = t, val = tot;
        if (t * p[pos] > now) 
          break;
    }
}
bool cmp(int x,int y){
    return Q[x]>Q[y];
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
      scanf("%lld", Q + i), tid[i] = i;
    sort(tid + 1, tid + n + 1,cmp);
    for (int i = 1; i <= n; i++){
        if (i > 1 && ans[tid[i - 1]] < Q[tid[i]])
          ans[tid[i]] = ans[tid[i - 1]];
        else{
            res = val = 1;
            now = Q[tid[i]];
            dfs(1, 1, 1, 1000);
            ans[tid[i]] = res;
        }
    }
    for (int i = 1; i <= n; i++)
      printf("%lld\n", ans[i]);
    return 0;
}