线性筛

模板

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
const int N=10000000;
const int mod=19260817;
using namespace std;

int num,prime[N],phi[N],flag[N],last[N],fac[N],rfac[N];

void exgcd(int a,int b,int& x,int& y)
{
	if(!b) {x=1;y=0;return;}
	exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-(a/b)*y; 
}

int get_inv(int a,int b)
{
	int x,y;
	exgcd(a,b,x,y);
	return (x%b+b)%b;
}

int cnt[N];
void crash(int x)
{
	memset(cnt,0,sizeof(cnt));
	while(x)
	{
		cnt[last[x]]++;
		x/=prime[last[x]];
	}
}

void pre()
{
	fac[1]=phi[1]=1; 
	for(int i=2;i<=100000;i++)
	{
		if(!flag[i])
		{
			prime[++num]=i;phi[i]=i-1;last[i]=num;
		}
		fac[i]=fac[i-1]*i%mod;
		rfac[i]=get_inv(fac[i],mod);
		for(int j=1;j<=num&&i*prime[j]<100000;j++)
		{
			int p=i*prime[j];
			flag[p]=1;last[p]=j;
			phi[p]=phi[i]*phi[prime[j]];
			if(i%prime[j]==0)
			{
				phi[p]=phi[i]*prime[j];
				break;
			} 
		}
	}
}

int main()
{
	pre();
	return 0;
}