寒假集训Day1 主要了解到了两个比较有意义的东西,记录如下
质数筛法
埃氏筛
从二开始,二是一个质数,那么二的倍数就是合数,三同理,利用这样的思想可以把所有质数的倍数做上标记
欧拉筛
埃氏筛有一个问题,就是同一个合数可能被反复筛选,比如6既是2的倍数又是3的倍数,这样它就会被筛选两遍。现在利用欧拉筛进行一个简化操作
对于我们找到的一个数,我们只需要标记所有已经找到的质数和该数的乘积即可,这样的筛选一直到这个数可以被其中一个已找到的质数整除为止,这样进行的欧拉筛复杂度应该是O(n)
代码如下:
bool isprime[1000009];
int prime[1000009];
int cnt;
void euler()
{
memset(isprime, true, sizeof(isprime));
isprime[1] = false;
for(int i = 2; i <= n; ++i)
{
if(isprime[i]) prime[++cnt] = i;
for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
{
isprime[i * prime[j]] = false;
if(i % prime[j] == 0) break;
}
}
}
哈希
目前只学了最基础的哈希,哈希可以看作一个对字符串加密的过程,我们希望用一个数值代表出整个字符串,让不同字符串的数值尽量不同。
因此我们需要一种转换方法,我们按照如下方法构造一个哈希函数:
我们把字符串看作一个h进制的数,每一个字符就相当于这个数的一位上的数,我们用进制转换的方法对字符串进行一个类似的操作,获得一个字符串的哈希值
const int B = 233;
const int M = 1e9 + 7;
string s;
int n;
int a[10000001] = { };
int ans = 0;
int main () {
scanf("%d" ,&n);
for(int i = 1;i <= n; i++) {
cin >> s;
int len = s.size();
int res = 0;
for(int j = 0;j < len; j++) {
res = (res * B + (s[j] - '0')) % M; //这里就比较像把B进制的数转化成10进制
}
a[i] = res;
}
标签:int,res,质数,Day1,寒假,哈希,字符串,isprime,集训
From: https://www.cnblogs.com/Crazyman-W/p/17966774