@[the_tool_er](/user/90706) 太感动了,竟然真的有人和我一样推莫反。。。
by wangjinbo @ 2021-06-19 22:20:28
@[SIXIANG](/user/298549) E去重用莫比乌斯函数自带的容斥就行
by Gary88 @ 2021-06-19 22:25:24
@[127_127_127](/user/341102) 其实这东西就是sg函数,只不过从数字扩展到局面了而已,F的局面就是所有没被覆盖的区间的sg函数的异或和,这个$O(s^2n)$递推就行,答案就是$[1,100)$的局面的sg函数
by Gary88 @ 2021-06-19 22:28:45
@[Gary88](/user/104963) 啊这/fad
那我弃坑了,不会莫比乌斯反演我爬了
但还是感谢巨佬 qwq
by SIXIANG32 @ 2021-06-19 22:33:05
@[SIXIANG](/user/298549) 不用莫比乌斯反演啊,你只要知道莫比乌斯函数的性质就行
我的代码:
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int T,n,m,k,tot,miu[1000001],vis[1000001],cnt;
int pri[1000002];
long long ans;
int main()
{
miu[1]=1;
for(int i=2;i<=1000000;i++)
{
if(!vis[i])pri[++cnt]=i,miu[i]=-1;
for(int j=1;j<=cnt&&i*pri[j]<=1000000;j++)
{
vis[i*pri[j]]=1;
if(i%pri[j])miu[i*pri[j]]=-miu[i];
else break;
}
}
int l,r;
scanf("%d%d",&l,&r);
for(int i=2;i<=1000000;i++)
{
int k=r/i-(l-1)/i;
if(!k)continue;
ans+=-1ll*miu[i]*k*(k-1)/2;
if(i>=l)ans-=r/i-1;
}
printf("%lld",ans<<1);
return 0;
}
```
by Gary88 @ 2021-06-19 22:45:39
@[Gary88](/user/104963) 不会莫比乌斯函数嘤嘤嘤
但还是谢谢大佬
然后您能帮我 hack 一下我 D 的贪心吗
好像大多数人都用并查集写了,我口胡了一个贪心,能帮我 hack 一下吗/kel
by SIXIANG32 @ 2021-06-20 10:43:01
@[SIXIANG](/user/298549) 你这是错的按秩合并并查集啊,hack数据也好构造,
```
input:
8
1 2 3 1 3 3 3 2
output:
2
```
by Gary88 @ 2021-06-20 14:55:26
@[Gary88](/user/104963) 谢谢
by SIXIANG32 @ 2021-06-20 15:00:43