AcWing 12478. E - 孪生质数
原题链接
简单
作者:
DPH
,
2021-03-21 19:32:55
,
所有人可见
,
阅读 337
/*
一个比埃筛更高效的板子
一个求分数取模的结论
一些之前不知道的知识 数组可以开1e7
一扒拉细节处理的失败经验
*/
#include <iostream>
using namespace std;
const long long N = 1e7 + 5;
const long long M = 1e9 + 7;
bool a[N] = {0};
long long b[N] = {0};
long long FastPower(long long base, long long power)
{
//如果底数大于M了 先%一下避免不必要的运算
base %= M;
long long result = 1;
while(power)
{
if(power & 1)
{
result = (result * base) % M;
}
power >>= 1;
base = (base * base) % M;
}
return result;
}
int main()
{
int o = 0;
a[0] = 1; a[1] = 1;
for(long long i = 2; i <= N; i++)
{
if(!a[i])
{
//i到1e7 i*i得开long long
for(long long j = i * i; j <= N; j += i) a[j] = 1;
}
if(!a[i - 2] && !a[i]) o++;
b[i] = o;
}
int t; cin>>t;
while(t--)
{
//这个n不开 long long 过不去 因为求x的时候会爆int
long long n; cin>>n;
long long s = b[n];
long long x = n * (n - 1) / 2;
long long ans = ((s%M)*(FastPower(x, M - 2)%M))%M;
cout<<ans<<'\n';
}
return 0;
}