题解 P1221 【最多因子数】

· · 题解

貌似现在的题解都被hack了，这个题是无解的，那就只能分块 + 打表了

不保证本程序会不会被卡TLE，但是不会WA

具体就是，把查询分成一些整体块和零散块（分块思想）

然后处理整体块时直接调用打好的表的数据，零散块暴力

那么首先肯定需要一个求任意数约数个数的函数：

inline int get(int x){//这个是求最小质因子
    for(int i = 2;i * i <= x;i++){
        if(x % i == 0) return i;
    }
    return x;//如果1 ~ sqrt(x)没有约数，那么这是个质数，返回自己
}

inline int calc(int x){
    int total = 1,cnt = 0;
    while(x != 1){
        int p = get(x);
        cnt = 0;
        while(x % p == 0){
            x /= p;
            cnt++;
        }
        total *= (cnt + 1);//常用的那个约数公式
    }
    return total;
}

然后考虑进行分块，块长一般是\sqrt n比较合适，然后写个暴力开始打表，具体大概这样：

for(i = 1;i <= 31623;++i){
        int id = L(i),ans = 0,tmp;//id是约数最多的数的编号，ans是约数数量
        for(j = L(i);j <= R(i);++j){
            tmp = calc(j);
            if(tmp > ans){
                id = j;
                ans = tmp;
            }
        }
        printf("%d,",id);
}

然后你就会发现怎么跑了2h还是没结果……，而且怎么表长轻轻松松超过50K交不了……

没错，这个时代，打表也需要优化了

首先先解决内存问题，先考虑调大块长减少打表数量，建议调到3 \times \sqrt n的样子，再大边角部分会TLE

然而这样还是会超

所以要先减去左边界，存与这个块左边界的差来压缩长度，再转字符串进一步压缩一下

注意不是所有ASCIL码都可以直接显示的，所以有些不能直接转

所以建议设计一套“密码”来转换，反正压到一个数三位就问题不大

然后优化下效率

现在分解质因数的效率显然太低了，可以直接线性筛出每个数的最小质因子，然后一直 /= 最小质因子，这样一个数只需要log(x)次就分解完了

实际上你肯定开不下10 ^ 9的数组，所以还得稍微改下

生成器：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define from(x) (((x) % 94866 == 0) ? ((x) / 94866) : ((x) / 94866 + 1))
#define L(x) (((x) - 1) * 94866 + 1)
#define R(x) ((x) * 94866)
int HIS[400000005];

inline int get(int x){
    for(int i = 2;i * i <= x;i++){
        if(x % i == 0) return i;
    }
    return x;
}

inline int calc(int x){
    if(x == 1) return 1;
    int total = 1,cnt = 0;
    int p = get(x);
    if(x <= 400000000) HIS[x] = p;

    do{
        cnt = 0;
        while(x % p == 0){
            x /= p;
            cnt++;
        }
        total *= (cnt + 1);
        if(x <= 400000000){
            p = HIS[x];
        }else{
            p = get(x);
        }
    }while(x != 1);
    return total;
}
char password[100] = {'#','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','1','2','3','4','5','6','7','8','9','0',';',':',',','.','(','?','<','>','[',']','{','}'};

inline char C(int x){
    return password[x];
}

inline int X(char c){
    for(int i = 0;i <= 74;i++){
        if(c == password[i]) return i;
    }
}

int main(){
    freopen("upd.cpp","w",stdout);
    HIS[1] = 1;
    for(int i = 2;i <= 400000000;i++){
        if(HIS[i]) continue;
        else HIS[i] = i;
        for(int j = i * 2;j <= 400000000;j += i){
            if(!HIS[j]) HIS[j] = i;
        }
    }
    register int i,j;
    for(i = 1;i <= 10541;++i){
        int id = L(i),ans = 0,tmp;
        for(j = L(i);j <= R(i);++j){
            tmp = calc(j);
            if(tmp > ans){
                id = j;
                ans = tmp;
            }
        }
        printf("%c%c%c",C((id - L(i)) / 5476),C((id - L(i)) / 74 % 74),C((id - L(i)) % 74));
    }
    return 0;
}

code：

#include <bits/stdc++.h>
using namespace std;
string answer("");//这里被和谐了

int l,r;

inline int get(int x){
    for(int i = 2;i * i <= x;i++){
        if(x % i == 0) return i;
    }
    return x;
}

inline int calc(int x){
    int total = 1,cnt = 0;
    while(x != 1){
        int p = get(x);
        cnt = 0;
        while(x % p == 0){
            x /= p;
            cnt++;
        }
        total *= (cnt + 1);
    }
    return total;
}

#define from(x) (((x) % 94866 == 0) ? ((x) / 94866) : ((x) / 94866 + 1))
#define L(x) (((x) - 1) * 94866 + 1)
#define R(x) ((x) * 94866)

char password[100] = {'#','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','1','2','3','4','5','6','7','8','9','0',';',':',',','.','(','?','<','>','[',']','{','}'};
int change[260];//快速还原，不然会TLE

char C(int x){
    return password[x];
}

int X(char c){
    return change[c];
}

int main(){
    for(int i = 0;i <= 74;i++){
        change[password[i]] = i;//预处理一下每个还原的位置
    }
    int id = 1,ans = 1;
    scanf("%d%d",&l,&r);
    int x = from(l),y = from(r);
    if(x == y){//特判相同块
        for(int i = l;i <= r;i++){
            int tmp = calc(i);
            if(tmp > ans){
                id = i;
                ans = tmp;
            }
        }
        printf("Between %d and %d, %d has a maximum of %d divisors.\n",l,r,id,ans);
        return 0;
    }
    for(int i = l;i <= R(x);i++){
        int tmp = calc(i);
        if(tmp > ans){
            id = i;
            ans = tmp;
        }
    }
    for(int i = L(y);i <= r;i++){
        int tmp = calc(i);
        if(tmp > ans){
            id = i;
            ans = tmp;
        }
    }
    for(int i = x + 1;i <= y - 1;i++){
        int Z = X(answer[3 * i - 2]) * 5476 + X(answer[3 * i - 1]) * 74 + X(answer[3 * i]);
        int Q = L(i) + Z;
        int tmp = calc(Q);
        if(tmp > ans){
            id = Q;
            ans = tmp;
        }
    }
    printf("Between %d and %d, %d has a maximum of %d divisors.\n",l,r,id,ans);
    return 0;
}

作为福利，顺便发一下打出来的表

你还可以来做做这个