题解 - [LightOJ 1370] Bi-shoe and Phi-shoe

发表于 更新于 分类于 ， 本文字数： 104 阅读时长 ≈ 1 分钟

题目链接

简述题意

给出一组数 \(a_i\), 对于每个数均可找到满足这样条件的数 \(f_i\): \(\varphi(f_i)\geqslant a_i\), 求

\[ \sum_{i=1}^n(f_i)_{min} \]

解题思路

根据 Euler 函数的性质，我们可以很容易地推知：对于 \(a_i\), 只要找不小于 \(a_i+1\) 的最小素数即可

代码

Show code

LightOJ_1370view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cmath>
#include <cstdio>
const int N = 1e6 + 5;
bool vis[N];
int main() {
  for (int i = 2; i * i < N; ++i)
    if (!vis[i])
      for (int j = i * i; j < N; j += i) vis[j] = 1;
  int kase;
  scanf("%d", &kase);
  for (int cnt = 1; cnt <= kase; ++cnt) {
    int n, _;
    scanf("%d", &n);
    long long tot = 0;
    while (n--) {
      scanf("%d", &_);
      while (vis[++_]);
      tot += _;
    }
    printf("Case %d: %lld Xukha\n", cnt, tot);
  }
}