西南科技大學題E孿生素數（考察點：歐拉篩、乘法逆元、快速冪或者擴展歐拉）
- 前言
- 一 題目描述
- 二 解題思路
- 三 題解代碼
- 四 總結
- 五 每日共勉
前言
上午剛看的繁佬的乘法逆元，下午的題正好考到了，還是卡了沒寫出來，總結模板＋模板題，歐拉篩模板，乘法逆元模板，快速冪模板，做個cv工程師就可以ac了，可惜我不配，一直wawawa，
賽前不努力，賽時哇哇哇，
一 題目描述
題目鏈接: link.
二 解題思路
1.歐拉篩（求出來孿生素數個數m）
2.乘法逆元（最后用于求解分數m/n mod 1e9+7的值，因為是分數不能直接模）
乘法逆元公式已經給了，
3快速冪（用于求解上面Q的mod-2次方問題），
？？？沒了？？？這就沒了？
好像是沒了，但是還剩下一句話，n個選取二個都是孿生素數的概率怎么算？
這個不會有人不會吧，巧了我就不會，
三 題解代碼
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e7+10;
int prime[maxx+10];//篩素數的陣列
int a[maxx+10];//n個數中有幾個孿生素數
bool vis[maxx+10];//標記陣列，0是i對應是素數，1是非素，
const int mod=1e9+7;//要模的值
typedef long long ll;
void init() //歐拉篩＋判斷n中有幾個孿生素數的打表，
{
vis[0]=vis[1]=1;
int k=0;
for(int i=2;i<=maxx;i++){
if(vis[i]==0)prime[++k]=i;
for(int j=1;i*prime[j]<=maxx;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
for (ll i = 0; i <= 10000000; ++i) {
a[i] = a[i - 1];
if (!vis[i] && !vis[i - 2]) {
++a[i];
}
}
}
ll ksm(ll a ,ll k) //快速冪
{
ll rec=1;
while(k)
{
if (k&1)
rec=((rec%mod)*(a%mod))%mod;
a=((a%mod)*(a%mod))%mod;
k>>=1;
}
return rec%mod;
}
int main()
{
ll n;
int t;
cin>>t;
init();
while(t--)
{
cin>>n;
//cout<<bj[n]<<" ";
cout<<(a[n])*ksm(n*(n-1)/2,mod-2)%mod<<endl;//我們從1～N中不放回地抽取兩個數，抽到的是孿生素數的概率.
}
return 0;
}
四 總結
作為數論選手的話個人覺得這些常用的模板得了然于心，雖然比賽可以帶模板，但是還是熟練敲出來好，畢竟cv工程師不太好，
五 每日共勉
千磨萬擊還堅勁，任他東南西北風，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271474.html
標籤：其他
上一篇：黑科技網站第三彈 懷舊游戲集錦