题解:P14073 [GESP202509 五级] 数字选取
题目传送门
题意
给定 \(1,2,3,4,\cdots,n\) 一共 \(n\) 个整数,从这些数中选取一些数字,使得选取的整数中任意两个不同的整数均互质。
数据规模与约定
对于所有测试点,保证 \(1 \le n \le 10^5\)。
算法 tag
质数、筛法。
题解
- 核心发现 \(1\):在这些数中,\(1\) 是必须选的,因为 \(1\) 与任何数的最大公因数都是 \(1\)。
- 核心发现 \(2\):任意两个不相等的质数一定互质,因为质数的因数只有 \(1\) 和它本身。
- 核心发现 \(3\):用合数替换其质因数,无法增加答案数量,因为合数一定包含至少一个质因数,若选合数则必须放弃其质因数(因它们不互质),但 \(1\) 个合数最多只能替代 \(1\) 个质因数,无法增加总数量。例如:选 \(4\)(质因数 \(2\))只能替代质数 \(2\),数量不变;选 \(6\)(质因数 \(2\)、\(3\))会替代 \(2\) 个质数,数量反而减少 —— 因此选质数比选合数更优。
综上,可以发现最优策略是 \(1\) 到 \(n\) 中的质数个数 \(+1\)(因为还有个 \(1\) 也是合法的)。
可以使用埃筛筛出 \(1\) 到 \(n\) 之间的质数,统计这些质数个数,再把答案 \(+1\)。
Code
void Solve(void)
{int n;cin>>n;vector<bool> is_prime(n+1,true);is_prime[0]=is_prime[1]=false; for(int i=2;i*i<=n;i++) {if(is_prime[i]){for(int j=2;i*j<=n;j++){is_prime[i*j]=false; } } }int ans=0;for(auto b:is_prime){if(b)ans++;}cout<<ans+1<<endl;
}