#P6656. [2019雅礼集训]sum
[2019雅礼集训]sum
[2019雅礼集训]sum
题目描述
从集合 中选出一个子集,使其中任意两个不同元素都互质,并最大化所选元素的和。
也就是说,所选子集 必须满足:对于任意不同的 ,都有 。
只需输出最大的元素和,无需输出子集。
输入格式
一行一个正整数 。
输出格式
一行一个正整数,表示满足条件的子集的最大元素和。
样例输入
10
样例输出
30
样例解释
可以选择 ,其中元素两两互质,元素和为 。
数据范围
| 数据比例 | 限制 |
|---|---|
从集合 {1,2,…,n} 中选出一个子集,使其中任意两个不同元素都互质,并最大化所选元素的和。
也就是说,所选子集 S 必须满足:对于任意不同的 u,v∈S,都有 gcd(u,v)=1。
只需输出最大的元素和,无需输出子集。
一行一个正整数 n。
一行一个正整数,表示满足条件的子集的最大元素和。
10
30
可以选择 {1,5,7,8,9},其中元素两两互质,元素和为 30。
| 数据比例 | 限制 |
|---|---|
| 20% | 1≤n≤30 |
| 50% | 1≤n≤200 |
| 80% | 1≤n≤800 |
| 100% | 1≤n≤200000 |