自动搬运

查看原文

来自洛谷，原作者为

	chenxinyang2006 退役了，生涯回忆有空的时候再写

搬运于2025-08-24 21:22:35，当前版本为作者最后更新于2020-01-21 23:32:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

貌似现在的题解都被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;
}

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

你还可以来做做这个