$「$数学基础$」$第$2$章 质数和约数
目录：

A.线性筛素数
B.质数距离
C.不定方程
D.反素数
E.余数之和

$A.$ 例题$1$ 线性筛素数

洛谷$link$

分析：

直接欧拉筛就行了

CODE：

#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=6e6+5;
int n,q,prime[N],tot;
bool isprime[100000005];
void Prime(int x)
{
	isprime[1]=0;
	for(int i=2;i<=n;i++)
	{
		if(isprime[i])
			prime[++tot]=i;
		for(int j=1;j<=tot&&i*prime[j]<=n;j++)
		{
			isprime[i*prime[j]]=0;
			if(i%prime[j]==0) 
				break;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&q);
	memset(isprime,1,sizeof(isprime));
	Prime(n);
	while(q--)
	{
		int k;
		scanf("%d",&k);
		printf("%dn",prime[k]);
	} 
	
	return 0;
}

$B.$ 例题$2$ 质数距离

洛谷$link$

分析：

在区间内筛出素数 然后依题意判断情况
找的时候就枚举就行了

CODE：

#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e6+5,M=(1<<17)+10;
ll l,r,tot,prime[N],prime2[N];
bool isprime[M],isprime2[N];
void Prime(int x)
{
	memset(isprime,1,sizeof(isprime));
	isprime[0]=isprime[1]=0;
	for(int i=2;i<=x;i++)
	{
		if(isprime[i]) prime[tot++]=i;
		for(int j=0;j<tot&&i*prime[j]<=x;j++)
		{
			isprime[i*prime[j]]=0;
			if(i%prime[j]==0) break;
		}
	}
}

int main()
{
	Prime(M);
	while(scanf("%lld%lld",&l,&r)!=EOF)
	{
		memset(isprime2,1,sizeof(isprime2));
		ll div;int cnt=0;
		for(int i=0;i<tot;i++)
		{
			div=l/prime[i];
			while(div*prime[i]<l||div<=1) div++;
			for(ll j=div*prime[i];j<=r;j+=prime[i])
				if(j>=l) isprime2[j-l]=0;
		}
		for(int i=0;i<=r-l;i++)
			if(isprime2[i]&&i+l>=2) prime2[cnt++]=i+l;
		if(cnt<2) puts("There are no adjacent primes.");
		else
		{
			ll min1,min2,max1,max2,minn=0x3f3f3f3f,maxn=-0x3f3f3f3f;
			for(int i=1;i<cnt;i++)
			{
				if(prime2[i]-prime2[i-1]<minn)
					min2=prime2[i],min1=prime2[i-1],minn=prime2[i]-prime2[i-1];
				if(prime2[i]-prime2[i-1]>maxn)
					max2=prime2[i],max1=prime2[i-1],maxn=prime2[i]-prime2[i-1];
			}
			printf("%lld,%lld are closest, %lld,%lld are most distant.n",min1,min2,max1,max2);
		} 
	}
	
	return 0;
}

$C.$ 例题$3$ 不定方程

洛谷$link$

分析：

一道推式子题 也是经典题了 重点是唯一分解定理
$blog$_$link$

$D.$ 例题$4$ 反素数

洛谷$link$

分析：

先确定质因子
$\because$ $2\times 3\times 5\times 7\times 11\times 13\times 17\times 19\times 23\times 29\times 31>2\times 10^9$
$\therefore$ 质因子取到$29$就可以了 也就是$1-N$中任何数质因子不会超过$10$个

若$n$为反素数 则有$n=(2^{c_1})(3^{c_2})(5^{c_3})(7^{c_4})......(29^{c_k})$ $c_i$满足单调递减
不然就会有约数个数相同 但不是最小的情况
然后就直接$dfs$了

CODE：

#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
int prime[12]={0,2,3,5,7,11,13,17,19,23,29};
ll n,ans,tmp;
void dp(ll dep,ll fac,ll a,ll b)
{
	if(fac>10) return;
	ll k=1;
	for(ll i=1;i<=dep;i++)
	{
		k*=prime[fac];
		if(a*k>n) return;
		if(b*(i+1)==tmp&&a*k<ans) ans=a*k;
		if(b*(i+1)>tmp)
		{
			tmp=b*(i+1);
			ans=a*k;
		}
		dp(i,fac+1,a*k,b*(i+1));
	}
}
int main()
{
	scanf("%lld",&n);
	dp(31,1,1,1);
	printf("%lld",ans);
	
	return 0;
}

$E.$ 例题$5$ 余数之和

洛谷$link$

分析：

暴力$O(n)$肯定过不了
$k$ $mod$ $i=k-\lfloor \frac{k}{i}\rfloor \times i$
$G(n,k)=n\times k-{\sum }_{i=1}^n\lfloor \frac{k}{i}\rfloor \times i$
然后整除分块就完了 $O(\sqrt{k})$

CODE：

#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
ll n,k,ans;
int main()
{
	scanf("%lld%lld",&n,&k);
	ans=n*k;
	for(ll l=1,r;l<=n;l=r+1)
	{
		if(k/l) r=min(k/(k/l),n);
		else r=n;
		ans-=(r+l)*(k/l)*(r-l+1)/2;  //(r+l)/2就是用整除分块*平均值
	}
	printf("%lld",ans);
	
	return 0;
}

最后

以上就是美好小鸭子为你收集整理的【Ybt OJ】[数学基础 第2章] 质数与约数分析：分析：分析：分析：分析：的全部内容，希望文章能够帮你解决【Ybt OJ】[数学基础 第2章] 质数与约数分析：分析：分析：分析：分析：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。