[LOJ#530]「LibreOJ β Round #5」最小倍数

[LOJ#530]「LibreOJ β Round #5」最小倍数

试题描述

第二天，LCR 终于启动了备份存储器，准备上传数据时，却没有找到熟悉的文件资源，取而代之的是而屏幕上显示的一段话：

您的文件存在被盗风险，为安全起见，您需要通过「智商·身份验证 ver. 5.0 β 版」的验证，以证明您是资料的主人。请写一个程序解决下述问题：

给定 \(p\)，求最小的正整数 \(n\)，使得 \(n! mod p = 0\)。

由于 \(p\) 很大，输入将给出 \(m\) 和 \(e_1, e_2, \cdots, e_m\)，表示 \(p = \prod_{i = 1}^{m}{\mathrm{pr}_i^{e_i}}\)，其中 \(\mathrm{pr}_i\) 是从小到大第 \(i\) 个质数。

一共有 \(T\) 个同样形式的问题需要解决。

输入

第一行包含一个正整数 \(T\) 表示数据组数。

每组数据第一行一个正整数 \(m\) 。

第二行包含 \(m\) 个非负整数，其中第 \(i\) 个数字表示 \(e_i(i = 1, 2, \cdots, m)\)，相邻两个数字之间恰好有一个空格。

输出

输出共 \(T\) 行，每行包含一个数字，表示该组数据的答案。

输入示例1

1
5
1 1 1 1 1

输出示例1

11

输入示例2

1
12
1 3 4 6 7 9 10 12 13 15 16 18

输出示例2

666

数据规模及约定

设 \(a_i = \mathrm{pr}_i \cdot e_i(i = 1, 2, \cdots, m)\)。

对于所有数据，\(1\leq T \leq 10^4, 1 \leq m \leq 100, 0 \leq a_i \leq 10^{18}\)。

题解

就我的俩 log 的二分会 T。。。

考虑怎么省去一个 log，我们不二分，还是考虑每个质数 \(p\)，设一个答案 \(N\)，则 \(N!\) 中包含 \(p\) 的个数为 \(\sum_{x=1}^{\infty}{\lfloor \frac{N}{p^x} \rfloor}\)。

这等价于把 \(N\) 变成 \(p\) 进制，设第 \(k\) 为 \(p\) 进制的值为 \(v\)，那么这位上的贡献就是 \((vv \cdots v)_p\)（即 \(p\) 进制下 \(k\) 个 \(v\) 的值），显然每一位上的贡献独立，于是预处理一下幂指数、前缀和啥的就可以 \(O(1)\) 算出 \(p\) 进制数上每一位的的值了。

然后对于 \(m\) 个质数分别做一遍，取最大值，记得还要和 \(1\) 取最大值。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define LL long long

LL read() {
	LL x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define N 1000
#define maxn 110
#define Range (LL)1e18

bool vis[N];
int cp, prime[N], cntp[maxn];
LL pown[maxn][maxn], full[maxn][maxn];
void init() {
	for(int i = 2; i < N; i++) {
		if(!vis[i]) prime[++cp] = i;
		for(int j = 1; j <= cp && prime[j] * i < N; j++) {
			vis[prime[j]*i] = 1;
			if(i % prime[j] == 0) break;
		}
	}
	for(int i = 1; i <= 100; i++) {
		pown[i][0] = 1;
		full[i][0] = 0;
		for(int j = 1; pown[i][j-1] <= Range / prime[i]; j++) {
			cntp[i] = j;
			pown[i][j] = pown[i][j-1] * prime[i];
			full[i][j] = full[i][j-1] + pown[i][j] - 1;
//			printf("full[%d][%d] = %lld\n", i, j, full[i][j]);
			if(full[i][j] + pown[i][j] - 1 > Range) break;
		}
	}
	return ;
}

void work() {
	int n = read();
	LL ans = 1;
	for(int i = 1; i <= n; i++) {
		LL need = read(), tmp = 0;
		if(need < 1) continue;
		int j;
		for(j = 1; full[i][j] < need; j++) ;
//		putchar('(');
		for(; j; j--) {
			LL now = (pown[i][j] - 1) / (prime[i] - 1), minx = (need - full[i][j-1] + now - 1) / now;
			tmp += minx * pown[i][j];
//			printf("[%lld - %lld + %lld - 1   %lld]", need, full[i][j-1], now, minx);
			need -= minx * now;
			if(need <= 0) break;
		}
//		printf("[0])%d %lld\n", prime[i], tmp);
		ans = max(ans, tmp);
	}
	printf("%lld\n", ans);
	return ;
}

int main() {
	init();

	int T = read();
	while(T--) work();

	return 0;
}