【例题 1】线性筛素数

核心代码：

inline void init() {
	memset(IsPrime,true,sizeof(IsPrime));
	IsPrime[1]=false;
	for(int i=2;i<=n;++i) {
		if(IsPrime[i])
			prime.push_back(i);
		for(int j=0;j<prime.size() && i*prime[j]<=n;++j) {
			IsPrime[i*prime[j]]=false;
			if(!(i%prime[j]))
				break;
		}
	}
}

代码中，外层枚举 (i) ，对于每一个 (i) ，如果它没有被筛掉，就是一个质数。我们再从内层枚举 (Prime_j) .(i times Prime_j) 是尝试筛掉的某个合数。其中，我们期望 (Prime_j) 是这个合数的最小质因数，循环中的 break 就做到了这一点。

理由（设 (Prime_t < Prime_s < Prime_j < Prime_l)：

(i) 的最小质因数肯定是 (Prime_j)
- 如果 (i) 的最小质因数是 (Prime_s) ，那么 (Prime_s) 更早被枚举到，因为我们枚举质数是从小到大的，当时就会被 break 掉。既然 (i) 的最小质因数是 (Prime_j) ，那么 (i times Prime_j) 的最小质因数肯定也是 (Prime_j) 。
(i times Prime_s) 的最小质因数是 (Prime_s)
- 如果它的最小质因数是 (Prime_t)，那么当然 (Prime_t) 会被更早枚举到，当时就要 break 。这说明 (j) 之前筛去的的数都是被最小质因数筛掉的。
(i times Prime_l) 的最小质因数一定是 (Prime_j)
- 因为 (i) 的最小质因数是 (Prime_j) ，所以 (i times Prime_l) 也含有 (Prime_j) ，所以最小质因数是 (Prime_j)。这说明如果 (j) 继续递增，所筛掉的数就不是用最小质因数筛掉的

【例题2】质数距离

思路：先筛出 (sqrt{R}) 之前的质数，再用这些质数筛掉 (L sim R) 中的合数。

代码：

#include <map>
#include <queue>
#include <cmath>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define swap(a,b) (a^=b^=a^=b)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const ll inf=1e18;
const int N=1e7+7;

struct node {
	ll dis,x,y;
	inline bool operator < (const node &y) const {
		return dis<y.dis;
	}
	inline bool operator > (const node &y) const {
		return dis>y.dis;
	}
}MaxAns,MinAns,tmp;

ll prime[N];
bool IsPrime[N],p[N];

ll L,R,tot;

inline void init(ll n) {
	tot=0;
	memset(IsPrime,true,sizeof(IsPrime));
	IsPrime[1]=false;
	for(ll i=2;i<=n;++i) {
		if(IsPrime[i])
			prime[++tot]=i;
		for(ll j=1;j<=tot && i*prime[j]<=n;++j) {
			IsPrime[i*prime[j]]=false;
			if(!(i%prime[j]))
				break;
		}
	}
}

signed main() {
	while(~scanf("%lld%lld",&L,&R)) {
		init(sqrt(R));
		memset(p,true,sizeof(p));
		MinAns.dis=inf,MaxAns.dis=-inf;
		for(ll i=1;i<=tot;++i)
			for(ll j=ceil(1.0*L/prime[i]);j<=floor(1.0*R/prime[i]);++j)
				if(j!=1 && prime[i]*j>=L) {
					p[prime[i]*j-L]=false;
					
				}
		if(L==1)
			p[0]=false;
		ll now=0;
		for(ll i=L;i<=R;++i)
			if(!now && p[i-L])
				now=i;
			else if(now && p[i-L]) {
				tmp={i-now,now,i};
				if(tmp<MinAns)
					MinAns=tmp;
				if(tmp>MaxAns)
					MaxAns=tmp;
				now=i;
			}
		if(MinAns.dis==inf)
			puts("There are no adjacent primes.");
		else
			printf("%lld,%lld are closest, %lld,%lld are most distant.n",MinAns.x,MinAns.y,MaxAns.x,MaxAns.y);
	}
    return 0;
}

【例题3】不定方程

因为

[dfrac{1}{x} + dfrac{1}{y} = dfrac{1}{n!} ]

所以

[y=dfrac{xn!}{x-n!} ]

设 (t=x-n!) ，则 (x=t+n!),得到

[y=n!+dfrac{(n!)^2}{t} ]

因为 (x,y in Z) ，所以 (t | (n!)^2)

所以题目的目标就变成了求 ((n!)^2) 的约数个数

代码就不放了

【例题4】反素数

思路：在约数个数相同的情况下尽可能地让当前数小，这个数就有可能是反素数。因为前 (10) 个素数的乘积 (> 2 times 10^9)，所以我们处理出前 (10) 个质数，暴搜即可。

代码：

// Problem: P1463 [POI2001][HAOI2007]反素数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1463
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <map>
#include <queue>
#include <cmath>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define swap(a,b) (a^=b^=a^=b)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int inf=0x3f3f3f3f;

const int a[17]={2,3,5,7,11,13,17,19,23,29};

int n,ans=1,maxx;

inline void dfs(int pos,int num,int sum,int lst) {
	if(sum>maxx || (sum==maxx && num<ans))
		ans=num,maxx=sum;
	if(pos>=10)
		return ;
	for(int j=1;j<=lst && a[pos]<=n/num;++j)
		dfs(pos+1,num*=a[pos],sum*(j+1),j);
}

signed main() {
	scanf("%d",&n);
	dfs(0,1,1,inf);
	printf("%d",ans);
    return 0;
}

【例题5】余数之和

依题意得， (ans = sum_{i=1}^{n} k bmod i)

因为

[a bmod b = a - b times lfloor dfrac{a}{b} rfloor ]

所以

[ans = sum_{i=1}^{n} k - i times lfloor dfrac{k}{i} rfloor = n times k - sum_{i=1}^{n} i times lfloor dfrac{k}{i} rfloor ]

那么问题就变成了求 (lfloor dfrac{k}{i} rfloor) 的值

我们打表试试

(i)	1	2	3	4	5	6	7	8	9	10
(lfloor dfrac{k}{i} rfloor)	5	2	1	1	1	0	0	0	0	0

我们发现这些值是一块一块分布的，其实我们只要某一块的左端点就可以找到右端点。

我们设 (t = lfloor dfrac{k}{i} rfloor) ，我们考虑它的左边界 (L) 与右边界 (R)

若 (t = 0) ，则 (R = n)

若 (t neq 0) ，则 (R = min(lfloor dfrac{k}{t} rfloor,n))

（请自行验证）

每一块的和 (=) 当前块的 $t times $ 当前块元素个数 (times) 当前块 (i) 的平均值

代码不放了

程序员灯塔
转载请注明原文链接：jidfbg