#P6656. [2019雅礼集训]sum

    ID: 6506 传统题 1000ms 1024MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-数论线性筛最小质因子预处理数据结构阈值划分大小情况贪心交换论证动态规划有限候选集缩减枚举与搜索全子集枚举可行性剪枝图论带权二分图匹配KM 算法CF3100

[2019雅礼集训]sum

[2019雅礼集训]sum

题目描述

从集合 {1,2,…,n}\{1,2,\ldots,n\} 中选出一个子集,使其中任意两个不同元素都互质,并最大化所选元素的和。

也就是说,所选子集 SS 必须满足:对于任意不同的 u,v∈Su,v\in S,都有 gcd⁡(u,v)=1\gcd(u,v)=1。

只需输出最大的元素和,无需输出子集。

输入格式

一行一个正整数 nn。

输出格式

一行一个正整数,表示满足条件的子集的最大元素和。

样例输入

10

样例输出

30

样例解释

可以选择 {1,5,7,8,9}\{1,5,7,8,9\},其中元素两两互质,元素和为 3030。

数据范围

数据比例 限制
20%20\% 1≤n≤301\le n\le30
50%50\% 1≤n≤2001\le n\le200
80%80\% 1≤n≤8001\le n\le800
100%100\% 1≤n≤2000001\le n\le200000