2024省选联测12

标签：13 12 17 省选 197 37 2024 && 101

A. 硬币

给定 \(n\)，在满足 \(x\times y = n^2+1\) 且 \(x,y\ge2\) 的前提下，最大化 \(x+y\)。

从后向前扫描序列，第 \(i\) 个数被扫到时为 \(p\)，\(p\) 为质数或者为 \(1\)。第 \(i+kp,k\in\mathbb{Z}\) 个数仍然是 \(p\) 的倍数。

因为

\[i^2+1\equiv 0\mod p \]

所以

\[(i+kp)^2+1\equiv i^2+1+2ikp+k^2p^2\equiv0\mod p \]

举例如下

\[\begin{aligned} 2 && 5&& 10&&17&& 26 &&37&& 50&& 65&& 82&& 101&& 122&& 145&& 170&&197&&226\\ 1 &&5&& 5&& 17&& 13 &&37 &&25 &&65 &&41&&101 &&61 &&145 &&85&&197&&113\\ 1 &&1&&5&&17&&13&&37&&5&&65&&41&&101&&61&&29&&85&&197&&113\\ 1&&1&&1&&17&&13&&37&&5&&13&&41&&101&&61&&29&&17&&197&&113\\ \end{aligned} \]

点击查看代码

for(int i = 1; i <= m; ++ i) p[i] = i * i + 1, a[i] = 1e18;

for(int i = 1; i <= m; ++ i)
{
    if(p[i] == 1) continue;

    a[i] = min(a[i], p[i]);

    for(int j = i + p[i]; j <= m; j += p[i])
    {
        a[j] = min(a[j], p[i]);
        while(p[j] % p[i] == 0) p[j] /= p[i];
    }
}

B. 猜数

你要从数集 \(1,2,\cdot\cdot\cdot ,n\) 中猜一个数，每次提问一个数 \(x\)，交互库会返回大于、小于或等于，代价为 \(x\)。
\(C(n)\) 表示在最优策略下的总成本。最优策略指的是在最坏情况下最小化总成本的策略。求 \(\sum_{i=1}^n C(n)\)。

\(f_{i,j}\) 表示从 \([i,j]\) 中猜数的成本。

\[f_{i,j}=\min(f_{i,j},\max(f_{i,k-1},f_{k+1,j})+k) \]

下课了 咕咕咕

标签：13,12,17,省选,197,37,2024,&&,101
From： https://www.cnblogs.com/Estelle-N/p/17971306