自动搬运

查看原文

来自洛谷，原作者为

	CarroT1212 chrono::system_clock::now().time_since_epoch().count()

搬运于2025-08-24 22:37:58，当前版本为作者最后更新于2022-05-02 09:48:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P8318 的题解大家可能都在抢着写，咱就不争了写个 P8319 吧

感觉这道题的题意写得不是很清晰，补充一下内容：

分子加上 1 之后，如果这个分数可以约分，一定要约分到最简形式；

约分不算操作次数；

现在小 D 给了你 $T$ 组数据，每组数据都是给定 $n$，求 $\max(f(1),f(2),\cdots ,f(n))$。

直接模拟每组数据显然是不可行的，会 T 飞。

那我们想一个问题：什么时候 $f(x)$ 的操作次数会最大？

来，看一下 $f(12)$ 的操作过程：

$\dfrac{0}{12}\rightarrow\dfrac{1}{12}\rightarrow(\dfrac{2}{12})\,\dfrac{1}{6}\rightarrow(\dfrac{2}{6})\,\dfrac{1}{3}\rightarrow\dfrac{2}{3}\rightarrow(\dfrac{3}{3})\,1$

共 5 步。

而 $f(11)$ 呢？

$\dfrac{0}{11}\rightarrow\dfrac{1}{11}\rightarrow\dfrac{2}{11}\rightarrow\dfrac{3}{11}\rightarrow\cdots\rightarrow(\dfrac{11}{11})\,1$

共 11 步。

$f(10)$ 呢？

$\dfrac{0}{10}\rightarrow\dfrac{1}{10}\rightarrow(\dfrac{2}{10})\,\dfrac{1}{5}\rightarrow\dfrac{2}{5}\rightarrow\dfrac{3}{5}\rightarrow\dfrac{4}{5}\rightarrow(\dfrac{5}{5})\,1$

共 6 步。

不难发现，约分次数越少，操作次数就越大。

因为每一次约分，分母都会变小，而分数值增加到 1，也就是分子增加到和分母一样大小的操作次数就会更少。

那什么时候约分次数会最小呢？

答：分母是质数的时候约分次数最小，即没有任何约分操作，这时 $f(x)$ 的操作次数就会等于分母。

所以这题就变成了一个素数筛的问题。

我们先跑一遍埃氏筛，然后对于每组数据，找最大的小于或等于 $n$ 的质数输出就可以了。特别且显然地，当 $n=1$ 时，答案就为 1。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
int t,n;
int flag[2000010];
void init() { //埃氏筛初始化
	for (int a=2;a<=2000000;a++) {
		if (flag[a]) continue;
		for (int b=a+a;b<=2000000;b+=a) flag[b]=1;
	}
}
int main() {
	cin>>t;
	init();
	while (t--) {
		cin>>n;
		for (int a=n;a;a--) { //循环找最大质数
			if (!flag[a]) {
				cout<<a<<endl;
				break;
			}
		}
	}
	return 0;
}

题外话：比赛时，我于 18:00:01 交了代码，于是 200pts -> 100pts，rank #400 -> rank #1300……