网站首页
编程语言
数据库
系统相关
其他分享
编程问答
USACO08DEC
2024-09-08
P2926 [USACO08DEC] Patting Heads S
根据题意我们不难想出枚举1到n,然后逐个判断能整除自己的个数,时间复杂度O(N^2),n<=1e5,明显会爆炸。考虑优化,我们看到a[i]<=1e6,可以开一个桶来记录,然后枚举1到maxn(即最大的a[i]),然后从i开始,每次加i,w[j](记录能整除j的a[i]的个数)+=c[i](值为i的个数)。代码:#include <bits/stdc