文章

68

粉丝

691

获赞

26

访问

577.8k

头像
素数筛法的灵活运用与取模函数的性质
P1066
发布于2020年5月10日 11:26
阅读数 7.2k

https://blog.csdn.net/csyifanZhang/article/details/106033659

↑更好的阅读体验

本题要求的,就是找一个最小的数m,使得任意两个数x,y,满足: 
(x mod m) != (y mod m). 
根据结论: 
当((x - y) mod m) != 0,则有:(x mod m) != (y mod m).

> 证明: 
设:a % m = b % m = k, 
则:a = p1 * m + k; b = p2 * m + k. 
(a - b) = (p1 - p2) * m,(a - b) mod m = 0. 
用反证,可以证明结论正确。

****
也就是说,我们要找到一个最小的因子,使得它不是任意两个数的差的因子。

 1. 最简单的做法,我们用$O(n^2)$的复杂度计算出来所有的差,并且对每个差计算他的所有因子,并记录。但是这样复杂度过高。
 2. 我们也可以将所有的差先计算出来,然后从小到大遍历所有的数,对每个数判断它是不是某个差的因子,这个过程类似于埃及筛法求素数的过程。

 

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<set>
using namespace std;

#define ll int
#define vec vector<ll>
#define MAX 5005
#define inf 0x3fffffff
#define P pair<ll,ll>

int main() {
	ll n, a[MAX], exist[1000005];
	while (cin >>...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发