温州网站开发风格,做影视剧组演员垂直平台网站,查营业执照怎么查询,鼓楼网页seo搜索引擎优化正题
题目链接:https://www.ybtoj.com.cn/contest/351/problem/1 题目大意
一个圆上#xff0c;你需要在3∼n3\sim n3∼n中选出kkk个作为aia_iai#xff0c;然后再圆上选择最少的点使得对于每个aia_iai你都能用选出的点连成一个正aia_iai边形。 k2≤n≤106k2\leq n\l…正题
题目链接:https://www.ybtoj.com.cn/contest/351/problem/1 题目大意
一个圆上你需要在3∼n3\sim n3∼n中选出kkk个作为aia_iai然后再圆上选择最少的点使得对于每个aia_iai你都能用选出的点连成一个正aia_iai边形。
k2≤n≤106k2\leq n\leq 10^6k2≤n≤106 解题思路
首先我们固定一个000点因为肯定所有的正aia_iai边形都交于一个点。
然后考虑对于一个aia_iai我们需要的点就是1ai×k(0≤kai)\frac{1}{a_i}\times k(0\leq ka_i)ai1×k(0≤kai)。
注意到一个aia_iai如果存在一个ajk×aia_jk\times a_iajk×ai那么aia_iai就不会产生贡献。反过来说aja_jaj的贡献会减少aia_iai。
而我们肯定是优先选择aia_iai的也就是说aja_jaj选择当且仅当它的所有约数都被选择而此时aja_jaj产生的贡献恰好就是φ(aj)\varphi(a_j)φ(aj)因为所有aja_jaj约数产生的贡献和为aja_jaj我们可以视为它们的贡献都单独为φ(x)\varphi(x)φ(x)
那么我们可以把3∼n3\sim n3∼n按照φ\varphiφ排序从小到大加就好了。
至于1,21,21,2特判一下比较小的情况就可以了kkk比较大时显然1,21,21,2会被选上去需要多选222个。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e610;
int n,k,cnt,phi[N],pri[N/10];
bool v[N];
int main()
{freopen(point.in,r,stdin); freopen(point.out,w,stdout);scanf(%d%d,n,k);if(k1)return puts(3)0;if(k2)return puts(6)0;phi[1]1;for(int i2;in;i){if(!v[i])phi[i]i-1,pri[cnt]i;for(int j1;jcnti*pri[j]n;j){v[i*pri[j]]1;if(i%pri[j]0){phi[i*pri[j]]phi[i]*pri[j];break;}phi[i*pri[j]]phi[i]*phi[pri[j]];}}sort(phi1,phi1n);long long ans0;for(int i1;ik2;i)ansphi[i];printf(%lld\n,ans);return 0;
}
