快乐的一天从AC开始 | 20210725 | P3653

题目链接

(补20210721)

机械键盘坏了,等发工资了就换新的,室友已经睡了,用笔记本自带的键盘也比较不吵

回想了一下上周,我也不清楚为什么两周经验的我会分到这么难的需求

下周好像要评绩效了,公司是OKR,我也不知道咋搞

算了算来上海也已经三周了,不过毕竟还算是新人,应该不至于背1吧

明天又要上班了,单休就这点不好,平时其实还算轻松。虽然是周六单休,但是其实最快乐的时候是周五早下班的时候,毕竟周六总想着明天又要上班了

心路历程

\(r - l \le 10^5\)

思路

虽然数字很大,但是范围很小,可以扫一遍

然后\(\mu\)的值只和素因子个数有关

如果筛掉一个整数\(10^6\)以内的素因子,那么剩下的素因子的乘积只有几种情况:变成1了,变成素数了,变成素数平方了,变成两个不同的素数的乘积。如果筛掉过后还有3个素因子那就超过范围了。筛的过程可以先欧拉筛,然后再区间筛(枚举素数,再枚举区间类素数的倍数)。

之后:

  • 如果是1,那么\(\mu\)不变
  • 如果是素数,那么\(\mu\)变成相反数,可以素性测试判断
  • 如果是素数平方,那么\(\mu\)变成0,这个就是判断完全平方数,sqrt一下再平方一下看看就可以了
  • 如果是两个不同的素数的乘积,那么\(\mu\)不变

注意可能会爆long long,龟速乘可能会T,可以用高效的乘法搞(指__int128_t

上一篇:李宏毅《机器学习》学习笔记5.2


下一篇:《统计学习方法》第9章习题