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

2023-08-09 17:29:40

[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

输入示例2

1

12

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

输出示例2

数据规模及约定

设 \(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;

}

码农公寓