Prime triplets (Project Euler 196)

original version

hackerrank programming version

题目大意是定义了一个正整数的表,第一行是1,第二行是1,2,第三行1,2,3...定义prime triple是在表上八连通的三个质数。然后问某行有多少个质数至少在一个prime triple中。   行数 <= 1e7.

题解:

假设要求第n行的答案,只要把上2行和下2行的数都抠出来,然后判断一下就好了。问题转化为求[L,R]之间的质数,这里5行数,区间长度大概有5e7,所以要用modified 区间筛法。 参考 http://euler.stephan-brumme.com/196/ 。 没什么思维量,积累一个区间筛法模板。

 #include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int mod = 1e9 + ; char* isPrime;
LL bias; vector<LL> eratosthenesOddSingleBlock(LL from, LL to)
{
vector<LL> primes;
if (from > to || to <= ) return primes;
if (to == )
{
primes.push_back();
return primes;
}
if (!(from & )) ++from;
if (from > to) return primes; if (from <= ) primes.push_back(), from = ;
const int memorySize = (to - from) / + ;
char* isPrime = new char[memorySize]; for (int i = ; i < memorySize; i++)
isPrime[i] = ;
for (LL i = ; i*i <= to; i+=)
{
if (i >= * && i % == )
continue;
if (i >= * && i % == )
continue;
if (i >= * && i % == )
continue;
if (i >= * && i % == )
continue;
if (i >= * && i % == )
continue;
LL minJ = ((from+i-)/i)*i;
if (minJ < i*i)
minJ = i*i;
if ((minJ & ) == )
minJ += i;
for (LL j = minJ; j <= to; j += *i)
{
int index = j - from;
isPrime[index/] = ;
}
} for (int i = ; i < memorySize; i++)
if (isPrime[i]) primes.push_back(from + *i); delete[] isPrime;
return primes;
} bool checkPrime(LL val)
{
return isPrime[val - bias];
} inline LL getNumber(int r, int c)
{
return 1LL * (r - ) * r / + c;
} bool checkCentre(int r, int c)
{
if (c < || c > getNumber(r, c) || !checkPrime(getNumber(r, c))) return false;
int cnt = , x, y;
for (int dx = -; dx <= ; ++dx)
{
for (int dy = -; dy <= ; ++dy)
{
x = r + dx;
y = c + dy;
if (y < || y > x) continue;
cnt += checkPrime(getNumber(x, y));
if (cnt >= ) return true;
}
}
return false;
}
bool check(int r, int c)
{
for (int dx = -; dx <= ; ++dx)
for (int dy = -; dy <= ; ++dy)
if (checkCentre(r + dx, c + dy))
return true;
return false;
} LL solve(int row)
{
if (row == ) return ;
if (row <= ) return ; LL l = getNumber(row - , ), r = getNumber(row + , row + );
vector<LL> primes = eratosthenesOddSingleBlock(l, r);
isPrime = new char[r - l + ];
memset(isPrime, , r - l + );
bias = l;
for (auto p: primes) isPrime[p - bias] = ; pair<int, int> pos;
LL res = , val = getNumber(row, );
for (int col = ; col <= row; ++col)
{
if (checkPrime(val) && check(row, col))
res += val;
++val;
}
return res;
} int main()
{
//freopen("out.txt", "w" , stdout); int a, b;
cin >> a >> b;
cout << solve(a) + solve(b) << endl; return ;
}
上一篇:抓包工具Fiddler的使用


下一篇:css3时钟