歐拉函數線性篩

對于素數$p$,
$$\phi (p?i)=?\begin{array}{ll}p?1& i=1\\ p?\phi (i)& p\mid i\\ (p?1)?\phi (i)& p?i\end{array}$$

證明：

$i=1$ 顯然

$i=1$根據

$\phi (i)=i\prod \frac{p_i?1}{p_i}$

$p\mid i$時除掉$i$中的$p$

$p?i$ 時除掉$p$

魔改歐拉篩素數即可

歐拉定理

當$(a,p)=1$

$a^{\phi (p)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$

即

$a^b\equiv a^{b\%\phi (p)}(\mathrm{m}\mathrm{o}\mathrm{d}p)$

擴展歐拉定理

當$b\ge \phi (p)$

$a^b\equiv a^{b\%\phi (p)+\phi (p)}(\mathrm{m}\mathrm{o}\mathrm{d}p)$

注意不要求互質

Miller Rabbin 算法

可以$O(lo{g}_x)$判斷素數（有極小概率出錯）

費馬小定理：$p$為素數，$a=p$,$a^{p?1}\equiv 1(mod\text{?}p)$

我有一個對這個命題的十分美妙的證明,可惜這里空白太小,我寫不下

二次探測定理：$p$為素數，$x^2\equiv 1(mod\text{?}p)$的解為$x=1$或$x=p?1$

證明見二次剩余

算法流程：設要判斷的數為$x$

特判$0,1,2$,偶數

取一個較小素數$p$,設$a,b$滿足$2^a\times b=x?1$

設$x^{\prime }\equiv p^b(mod\text{?}x)$,不斷取平方并對$x$取模，若結果為$1$，用二次探測判斷。

重復$a$次后$x^{\prime }\equiv p^{x?1}(mod\text{?}x)$，用費馬小定理判斷

例題：hdu2138 How many prime numbers

題意：給$N$個數，數數有多少個素數

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> typedef long long ll; using namespace std; int qpow(int a,int p,int m) {int ans=1;while (p){if (p&1) ans=((ll)ans*a)%m;a=((ll)a*a)%m,p>>=1;}return ans; } int pri[]={2,3,5,7,11,13,17,19,23,29}; bool check(int x) {if (x==2) return true;if (!(x&1)) return false;int a=0,b=x-1;while (!(b&1)) ++a,b>>=1;for (int i=0;pri[i]<x&&pri[i]<29;i++){int now=qpow(pri[i],b,x);for (int j=1;j<=a;j++){int t=((ll)now*now)%x;if (t==1&&now!=1&&now!=x-1) return false;now=t;}if (now!=1) return false;}return true; } int main() {int n;while (~scanf("%d",&n)){int ans=0,x;while (n--){scanf("%d",&x);ans+=check(x);} printf("%d\n",ans);}return 0; }

關于底數選擇：

以$2,3,7,61,24251$為底，$1e16$內唯一無法判斷的合數為$46856248255981$

特判一下就可以了

代碼不想改了

Pollard-Rho算法

這個算法就更玄學了，可以極快分解質因數。

有多快呢？$long\text{?}long$能跑幾百個

該算法核心是找到這個數的一個非平凡因子（即不是$1$和本身，以下簡稱因子），然后遞歸就行了

如何找到一個因子呢？ 隨機。

當然直接隨機肯定不現實，需要一定的改進

①優秀的隨機函數

定義隨機函數$f_i=f_{i?1}^2+c$，其中$c$為隨機常數。

至于為什么要選這個函數……鬼知道啊

②$gcd$

設給定的數為$x$，我們要找的是$d\mid x$

概率還是低了點

容易想到一個辦法：取$gcd$，大于$1$就返回$gcd$的值

這樣多了因數的倍數，很大的提高了概率

③倍增路徑

每次取一段$2^k$個數，在模$x$乘起來，最后取$gcd$,$k$為當前段數

易知這樣是等效的，避免了大量的$gcd$計算

使用了倍增，將$gcd$次數從$O(n)$降至$O(logn)$

另外不再使用隨機值，而是用隨機出來的值和上一段最后一個數作差，這樣得到數的個數也大幅增加。

這樣除非環特別短，否則環上兩兩的數都會統計入答案。

根據生日悖論，當環長為45時找不到答案的概率小于$1e?18$

而你的函數是根據$C$改變的，所以根本卡不了

所以如果出鍋了，自覺去交一發Hash Killer III

④玄學優化

每一段跑$127$個數更新一次

親測快了$3$倍

來自$luogu$題解區

原理就不得而知了

結合$Miller?Rabbin$食用更佳

例題：luogu模板

題意：給個數，是素數輸出"Prime"，不是素數輸出最大質因數

遞歸，記個全局變量。還可以剪枝。

運用你豐富的卡常技巧就可以通過此題

// luogu-judger-enable-o2 #include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cstdlib> #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif typedef long long ll; using namespace std; inline ll read() {ll ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } ll base[]={2,3,7,61,24251}; inline ll qmul(const ll& a,const ll& b,const ll& m) {ll ans=a*b-(ll)((long double)a*b/m+0.5)*m;return ans<0? ans+m:ans; } inline ll qpow(ll a,ll p,const ll& m) {ll ans=1;while (p){if (p&1) ans=qmul(ans,a,m);a=qmul(a,a,m),p>>=1;}return ans; } inline bool Miller_Rabbin(const ll& x) {if (x==1) return false;if (x==2) return true;if (!(x&1)) return false;if (x==46856248255981ll) return false;int a=0;ll b=x-1;while (!(b&1)) ++a,b>>=1;for (register int i=0;i<5&&base[i]<x;i++){ll now=qpow(base[i],b,x);for (register int j=1;j<=a;j++){ll t=qmul(now,now,x);if (t==1&&now!=1&&now!=x-1) return false;now=t;}if (now!=1) return false;}return true; } ll ans; inline ll f(const ll& x,const ll& c,const ll&m){return (qmul(x,x,m)+c)%m;} inline ll gcd(ll x,ll y) {static ll t;while (y>0) t=y,y=x%y,x=t;return x; } inline ll abso(const ll& x){return x>0? x:-x;} inline ll Pollard_rho(const ll& x) {ll s=0,t=0,c=rand()%(x-1)+1,d,len=1,m=1,i;for (;;len<<=1,s=t,m=1){for (i=1;i<=len;i++){t=f(t,c,x);m=qmul(m,abso(t-s),x);if (i%127==0&&(d=gcd(m,x))>1) return d;}if ((d=gcd(m,x))>1) return d;} } inline void fact(const ll& x) {if (x<ans) return;if (Miller_Rabbin(x)) return (void)(ans=max(ans,x));ll d=Pollard_rho(x);if (Miller_Rabbin(d)) ans=max(ans,d);else fact(d);d=x/d;if (Miller_Rabbin(d)) ans=max(ans,d);else fact(d); } int main() {register int T;ll n,d;scanf("%d",&T);while (T--){n=read();ans=0,fact(n),d=ans;if (n==d) printf("Prime\n");else printf(lld"\n",ans);}return 0; }

原根

占個坑以后補

二次剩余

以下的$p$均為奇素數

定義：方程$x^2\equiv n(mod\text{?}p)$有解,稱$n$是$mod\text{?}p$意義下的二次剩余，否則稱非二次剩余

說人話：在$mod\text{?}p$下可以開根號

勒讓德符號

$$(\frac{n}{p})=?\begin{array}{ll}1& \text{n是p的二次剩余}\\ ?1& \text{n是p的非二次剩余}\\ 0& p\mid n\end{array}$$

如無特別說明，下文分數+括號均為勒讓德符號

引理

$(\frac{n}{p})\equiv n^{\frac{p?1}{2}}(mod\text{?}p)$

(強調：$p$是奇素數)

證明：

當$n$是$p$的二次剩余，設$x^2\equiv n(mod\text{?}p)$,則$n^{\frac{p?1}{2}}\equiv x^{p?1}(mod\text{?}p)$。由費馬小定理，$x^{p?1}\equiv 1(mod\text{?}p)$

當$n$是$p$的非二次剩余，即不存在$x^2\equiv n(mod\text{?}p)$。對于任意的$a$,由于$a^2=n(mod\text{?}p)$,所以$a=a^{?1}n$。而逆元是互逆的，這樣可以把$p?1$個數配成$\frac{p?1}{2}$對，每對數的積為$n$。將所有數乘起來，$(p?1)!\equiv n^{\frac{p?1}{2}}(mod\text{?}p)$。由威爾遜定理，$(p?1)!\equiv ?1(mod\text{?}p)$

$p\mid n$,顯然成立

引理

共有$\frac{p?1}{2}$個$n$是$p$下的二次剩余

證明：設兩個數$u,v$滿足$u=v,u^2\equiv v^2(mod\text{?}p)$,即$p\mid u^2?v^2=(u+v)(u?v)$

故$p\mid u+v$,反之同理

說人話：有且僅有模意義下的相反數平方相同。

所以$x^2$共有$\frac{p?1}{2}$個不同取值

所以隨機出一個（非）二次剩余是$O(1)$的

引理

$(a+b{)}^p\equiv a^p+b^p(mod\text{?}p)$

二項式定理展開即可，不再證明。

重頭戲開始。坐穩了，前方高能！

隨機一數$a$，若$(\frac{a^2?n}{p})=?1$,令$w=\sqrt{a^2?n}$,則$(a+w{)}^{\frac{p+1}{2}}$是方程$x^2\equiv n(mod\text{?}p)$的根

什么？$a^2?n$不是非二次剩余嗎？怎么開根？

沒辦法啊……那就類比虛數，定義$z=a+bw$吧（絕對不是人想出來的）

引理

$w^p\equiv ?w(mod\text{?}p)$

證明：$w^p\equiv w^{p?1}w\equiv (a^2?n{)}^{\frac{p?1}{2}}w\equiv (\frac{a^2?n}{p})w\equiv ?w（mod\text{?}p）$

最后證明：

$x^2\equiv (a+w{)}^{p+1}\equiv (a+w{)}^p(a+w)\equiv (a^p+w^p)(a+w)=(a?w)(a+w)=a^2?w^2\equiv n(mod\text{?}p)$

證畢……

哎等等？$x$是虛數怎么辦？

假設$x$是虛數，設$x=a+bw$(不是上面的$a$) 由$x$定義，$a=0$

$x^2=a^2+b^2{w}^2+2abw=a^2+a^2{b}^2?n{b}^2+2abw$是虛數，而$n$是實數。

假設不成立，所以$x$是實數(并不嚴謹)

例題：Timus OJ1132 Square Root

數據很小，暴力能過。但只有這題，將就了吧。

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cstdlib> #define int long long using namespace std; struct complex{int x,y;}; int n,w2,p; inline complex operator *(const complex& a,const complex& b){return (complex){(a.x*b.x%p+a.y*b.y%p*w2%p)%p,(a.x*b.y%p+a.y*b.x%p)%p};} inline complex qpow(complex a,int b) {complex ans;ans.x=1,ans.y=0;while (b){if (b&1) ans=ans*a;a=a*a,b>>=1;}return ans; } inline int qpow(int a,int b) {int ans=1;while (b){if (b&1) ans=ans*a%p;a=a*a%p,b>>=1;}return ans; } inline int lerender(const int& x){return qpow(x,p>>1);} int solve() {if (lerender(n)==p-1) return -1;int a;while (true){a=rand()%p;w2=(a*a-n)%p;if (w2<0) w2+=p;if (lerender(w2)==p-1) break;}complex res;res.x=a,res.y=1;res=qpow(res,(p+1)>>1);return res.x; } inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } void write(const int& x) {if (x<10) return(void)putchar(x^48);int t=x/10;write(t),putchar((x-(t<<1)-(t<<3))^48); } main() {int T=read();while (T--){n=read(),p=read();if (p==2) {printf("1\n");continue;}int ans=solve();if (ans==-1) printf("No root\n");else{int ans2=p-ans;if (ans>ans2) swap(ans,ans2);write(ans),putchar(' '),write(ans2),putchar('\n');}}return 0; }

總結

以上是生活随笔為你收集整理的中高级数论 [欧拉函数线性筛，二次剩余]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。