别着急,坐和放宽
使用社交账号登录
有函数 定义如下:
这里序列 是正整数 的所有真约数(去重)的升序排列,求
我们先用样例 打表看看有什么规律:
我们发现,其求和可以变成,
不难发现对于某个因子 对于整体的贡献,就是其对于某个数 的升序排序的次序。例如因子 ,其整除的数有 在这三个数的因子排序都是第2个,所以其贡献是 。
那么我们可以根据这个发现,先枚举 的所有因子 ,然后枚举其倍数 ,作一个计数器用于记录其出现的次数,然后根据其出现的次数作贡献即可。
即使用埃氏筛的思想,枚举倍数
[!NOTE]
这里还可以思考下是否存在 的线筛做法,我的思路是把每个数作质因数分解,看看是否存在递推(或者化归) 或者 的性质,然后就可以预处理质因数的 然后递推了。
但是我代几个数发现似乎并不存在这样的性质,所以这里就不展开了。
这里外循环 次,然后内循环每个 执行 次 ,总的次数是,
即时间复杂度是 在2e6下还是可以过的
我们知道了枚举倍数的筛思想,下面引出埃氏筛(筛质数):
埃氏筛是一种用于筛选质数的算法,其思路是:如果一个数 是质数,那么它的倍数 一定不是质数。因此,我们可以从 开始,依次标记每个质数的倍数,最后剩下的数就是质数。
由于埃氏筛只对质数进行倍数枚举,其时间复杂度是
[!TIP]
类似的题目:
- [GESP202509 五级] 数字选取
筛质数模板题(大雾- Bitwise Or vs LCM
这里要点放缩的小巧思- [Brooklyn Round 1 & NNOI Round 1 A] Flying Flower
找到最优策略就好
using ll = long long;
void sol()
{
ll n; scanf("%lld",&n);
ll s=n; // 先把1的贡献记上
int cnt[n+1]; //当然还可以使用bool省空间
memset(cnt,0,sizeof(cnt));
for(ll i=2; i<=n; i++)
{
ll t=i*i;
s+=(cnt[i]&1? -t:t);
cnt[i]++;
for(ll j=2*i; j<=n; j+=i)
{
s+=(cnt[j]&1? -t:t);
cnt[j]++;
}
}
printf("%lld",s);
return;
}