一、埃式篩（計算質數）
1.1、概念
1.1.1、在傳統的計算質數中，我們采用單點判斷，即判斷(2~sqrt(n))是否存在不合法元素，若存在則判否，否則判是
1.1.2、假設，此時我們需要求1~1000的所有質數，此方法的時間復雜度就會變成O(n*sqrt(n)),這顯然太過冗余了
- 因此，我們可以使用埃式篩
1.1.3、現在，求1~20中的所有質數，我們就可以：
-
1)首先將0、1排除：
-
2)創建從2到n的連續整數列表，[2,3,4,…,n]；
-
3)初始化 p = 2，因為2是最小的質數；
-
4)枚舉所有p的倍數(2p,3p,4p,…)，標記為非質數（合數）；
-
5)找到下一個 沒有標記 且 大于p 的數。如果沒有，結束運算；如果有，將該值賦予p，重復步驟4;
-
6)運算結束后，剩下所有未標記的數都是找到的質數。
-
此時，
2是第一個質數，因此把2的倍數全部設置為1(vis[j]=1)將其全部篩出
-
接下來，發現
3為0，表示3是一個質數，因此我們把3的倍數也給篩掉
-
因此，我們可以發現只要其沒有被其他數字篩掉，那么他就一定是質數
1.2、總結：
ll vis[N];//用來判斷一個數是否被篩掉了，0->沒被篩掉,1->篩掉
void solve()
{ll n;cin>>n;vis[0]=vis[1]=1;for(ll i=2;i<=n;i++)//從2開始篩值{//從i*2開始，每次+i,當枚舉到還沒篩掉的數，篩掉for(ll j=i*i;j<=n;j+=i) {if(vis[i]==0) vis[j]=1;}}for(ll i=2;i<=n;i++) if(vis[i]==0) cout<<i<<' ';
}
2、最大公約數(gcd)和最小公倍數(lcm)
2.1、gcd求法
2.1.1、如何求解兩個數(a,b)的最大公約數(gcd)？
- 使用輾轉相除法
- 首先 ，我們假設(a>b)，通過數學公式不難得出：
- 1)
gcd(a,b)=gcd(a%b,b)，比如gcd(18,6)=gcd(0,6) - 2)
if(b==0)那么意味著此時的a即為最小公倍數
- 因此，代碼可以寫成
ll gcd(ll a,ll b) //只需記住，無論何時：a>b
{return b==0 ? a : gcd(b,a%b);
}
2.2、lcm求法
2.2.1、如何求解兩個數(a,b)的最小公倍數(lcm)？
- 只需記住一個公式即可：
a*b=gcd(a,b)*lcm(a*b);
3、快速冪
3.1、概念：求解ab
- 1、當
b為奇數時候，拆出一個a，此時，b就變成了一個偶數 - 2、當
b為一個偶數的時候，就拆出其次方項b-->2/b
3.1.1、代碼實現
//快速冪
ll qmi(ll a,ll b,ll c) //a ^ b % c
{int res=1;while(b){if(b&1) res=res*a%c,b--;//當b是奇數時，拆出一個a,使得 b 變成偶數else a=a*a%c,b>>=1; //此時b為偶數，拆出一個a*a，等待下次為奇數再計算答案}return res;
}
四、乘法逆元
4.1、概念
- 在寫題目的時候，假設我們需要表達
a/b，是不好表達的，只能用浮點數來表示，因此我們就采用乘法逆元(類似于倒數 % p)來表示
4.2、那么，如何來求逆元呢？
- 我們可以使用費馬小定理來求解
4.3、乘法逆元例題
- 題目鏈接
4.3.1、對于例題，我們可以對這個分式進行分解
- 因此，我們可以使用逆元來表示分數即可
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 2e5 + 7;
ll p=998244353;ll qmi(ll a,ll b) //快速冪
{ll res=1;while(b){if(b&1) res=res*a%p,b--;a=a*a%p,b>>=1;}return res%p;
}ll inv(int x) //求解x的逆元
{return qmi(x,p-2)%p;
}void solve()
{ll a,b,c,q;cin>>a>>b>>c>>q;while(q--){ll x;cin>>x;cout<<(a*x%p+b)%p*inv(c*x%p)%p<<'\n'; }
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1; cin>>_;while (_--) solve();return 0;
}
)
