怎么可以做网站,互助资金盘网站开发,百度网站上传,近期新闻热点大事件欧拉函数
定义#xff1a;小于或等于n的正整数中与n互质的数的数目#xff0c;例如#xff1a;φ(8)4#xff0c;1#xff0c;3#xff0c;5#xff0c;7与8互质。
通式#xff1a;(其中p1, p2……pn为x的所有质因数#xff0c;x是不为0的整数)
性质#xff1a;
…欧拉函数
定义小于或等于n的正整数中与n互质的数的数目例如φ(8)41357与8互质。
通式(其中p1, p2……pn为x的所有质因数x是不为0的整数)
性质
p为质数,m为大于0自然数
φ( p)p-1
欧拉函数是积性函数——若m,n互质
if(m%p0) φ(p*m) φ(m)*p
else φ(p*m) φ( p)*φ(m)
if(m1) φ(2*m) φ(m)
else if(m2)φ(m)为偶数
φ(pm)φ(pm)-φ(pm-1)
求和 Σ d ∣ n n Σ_{d|n}n Σd∣nn Σ i 1 n [ g c d ( i , n ) 1 ] φ ( n ) Σ^{n}_{i1}[gcd(i,n)1]φ(n) Σi1n[gcd(i,n)1]φ(n) Σ i 1 n i [ g c d ( i , n ) 1 ] ⌈ φ ( n ) ∗ n 2 ⌉ Σ^{n}_{i1}i[gcd(i,n)1]⌈\frac {φ(n)*n}{2}⌉ Σi1ni[gcd(i,n)1]⌈2φ(n)∗n⌉ 麻瓜(我)的求法
int gtpi(int n){int res1;for(int i2;in;i)if(__gcd(i,n) 1)res;return res;
}O(sqrt(n))求φ(n)
int phi(int n){//if(n0)return 0;int resn,tmpn;for(int i2;i*itmp;i){if(tmp%i0){resres/i*(i-1);while(tmp%i0)tmp/i;}}if(tmp1)resres/tmp*(tmp-1);return res;
}O(n)求1~n所有数的欧拉函数
const int N;
int prime[N],cnt;
int phi[N];
bool vis[N];void Get_phi(int n){phi[1]1;for(int i2;in;i){if(!vis[i]){prime[cnt]i;phi[i]i-1;//性质1}for(int j0;prime[j]n/i;j){int tprime[j]*i;vis[t]1;if(i%prime[j]0){phi[t]phi[i]*prime[j];//性质2break;}phi[t]phi[i]*(prime[j]-1);//性质2}}
}欧拉定理
定义 欧拉定理Euler Theorem也称费马-欧拉定理或欧拉函数定理是一个关于同余的性质。 内容 若n,a为正整数且n,a互质则: a ϕ ( n ) ≡ 1 ( m o d n ) a ^{\phi(n)} \equiv 1(mod\;n) aϕ(n)≡1(modn)
费马小定理 若n,a为正整数且n为质数则: a ϕ ( n ) ≡ 1 ( m o d n ) a n − 1 ≡ 1 ( m o d n ) a ^{\phi(n)} \equiv 1(mod\;n)\;\;a ^{n-1} \equiv 1(mod\;n) aϕ(n)≡1(modn)an−1≡1(modn)
逆元 a ϕ ( n ) − 1 a^{\phi(n)-1} aϕ(n)−1
证明 设x1x2…x(φ(n))是一个以n为模的缩系 则ax1ax2…axφ(n) 也是一个以n为模的缩系因为an1。 于是有ax1ax2…axφ(n) ≡x1x2…x(φ(n))mod n 所以a^φ(n) ≡ 1 (mod n)。证毕。 欧拉降幂
显然 a b ≡ { a b % ϕ ( p ) if g c d ( a , p ) 1 a b if g c d ( a , p ) ̸ 1 , b ϕ ( p ) ( m o d p ) a b % ϕ ( p ) ϕ ( p ) if g c d ( a , p ) ̸ 1 , b ϕ ( p ) a^b \equiv \begin{cases} a^{b\%\phi(p)} \text{if } gcd(a,p)1 \\ a^b \text{if } gcd(a,p)\not1,b\phi(p) \text{ }(mod\;p)\\ a^{b\%\phi(p)\phi(p)} \text {if }gcd(a,p)\not1 ,b\phi(p) \end{cases} ab≡⎩⎪⎨⎪⎧ab%ϕ(p)abab%ϕ(p)ϕ(p)if gcd(a,p)1if gcd(a,p)1,bϕ(p)if gcd(a,p)1,bϕ(p) (modp) 然后就可以愉快地做题了 例如 牛客的 简单数据结构1 Ternary String 子序列 [SDOI2008]仪仗队洛谷也有一样的 但好像数据不太一样
