P8319 Sol

· · 题解

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 步。

$\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……