【板子】数论基础（持续更新ing...）

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=3000050;

int phi[maxn],prime[maxn],tot;

bool notprime[maxn];

void isprime(int x){

	if(x<2)return 0;

	for(int i=int(sqrt(x+0.5));i>=2;i--){

		if(x%i==0)return 0;

	}

	return 1;

}//判断素数

int prime[maxn],tot;

bool nowprime[maxn]={1,1};

void xxs(int n){

	for(int i=2;i<=n;i++){

		if(!nowprime[i])prime[++tot]=i;

		for(int j=1;j<=tot&&i*prime[j]<=n;j++){

			notprime[i*prime[j]]=1;

			if(i%prime[j]==0)break;

		}

	}

}//线性筛

int euler(int n){

	int m=int(sqrt(n+0.5));

	int ans=n;

	for(int i=2;i<=m;i++){

		if(n%i==0){

			ans=ans/i*(i-1);

			while(n%i==0)n/=i;

		}

	}

}//求n的欧拉函数值

int n,phi[maxn],prime[maxn],tot;

bool notprime[maxn];

void getphi(){

	int i,j,k;

	phi[1]=1;

	for(i=2;i<=n;i++){

		if(!notprime[i])prime[++tot]=i,phi[i]=i-1;

		for(j=1;j<=tot;j++){

			k=i*prime[j];

			if(k>n)break;

			notprime[k]=1;

			if(i%prime[j]==0){

				phi[k]=prime[j]*phi[i];break;

			}else{

				phi[k]=(prime[j]-1)*phi[i];

			}

		}

	}

}//求1-n的所有欧拉函数值

int main(){

}
巴特西

【板子】数论基础（持续更新ing...）

最新文章

热门文章
