线性筛怎么写来着

不会真的有人考场上想不起来线性筛这么写吧你说是吧郑地

这道题其实想要告诉我们线性筛其实可以筛很多奇奇怪怪的东西，就例如本题的这个函数

首先我们易得一个性质：当$gcd(x,y)==1$时，$f(x\times y)=f(x)\times f(y)$，因为$x$和$y$之间没有相同的质因子，所以可以乘算(变成了积性函数)

所以对于筛质数的时候，我们就可以把$f$函数线性计算出来

现在考虑$gcd(x,y)\neq 1$的时候，因为在筛质数的时候，每个合数只会被它的最小质因数筛一次，所以我们可以记录非质数数的最小质因子数量，新的数的此质因子数量就是它加上一

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< ll,ll >

const int N=2e7+10;

ll f[N];
pii vis[N];
vector< ll > prime;  

void euler( ll upper )
{
	f[1]=1;
	for( int i=2;i<=upper;i++ )
	{
		if( !vis[i].first )
		{
			f[i]=1, vis[i]={ i,1 }, prime.push_back( i );
		}
		for( auto x:prime )
		{
			if( 1ll*i*x > upper ) break;
			f[i*x]=f[i];
			vis[i*x]={ x,1 };
			if( i%x == 0 ){ f[i*x]=( f[i]/vis[i].second )*( vis[i].second+1 ), vis[i*x].second=vis[i].second+1;break; }
		}
	}
}

int main()
{	
//	freopen( "txt.in","r",stdin );
	std::ios::sync_with_stdio( false );
	cin.tie( nullptr );
	cout.tie( nullptr );
	int n;
	cin>>n;
	euler( n );
	ll ans=0;
	for( int i=1;i<=n;i++ ) ans^=f[i];
	cout<<ans;
}