(补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