欧拉函数和快速幂
欧拉函数：定义：
互质：互质是公约数只有1的两个整数，叫做互质整数。
欧拉函数：欧拉函数，即 体现的是小于等于n并且和n互质的数的个数。
好比说 φ(1) = 1。当n是质数的时候，显然有 (n)=n-1。
如何求1~n中和n互质的数的个数？
容质原理：
1.从1~n中去掉p1，p2....pk的倍数（此时可能存在多去的环境，例如一个数既是p1的倍数又是p2的倍数）
2.加上全部pi*pj的倍数（此时如果一个数既是p1，p2的倍数又是p3的倍数，此时加三次减三次，没有变化但我们需要去除）
3.减去全部pi*pj*pk
4.加上pi*pj*pk*pd....
依次类推合并得到
https://latex.csdn.net/eq?%5Cphi%20%28n%29%20%3D%20n%20%281-%5Cfrac%7B1%7D%7Bp1%7D%29%281-%5Cfrac%7B1%7D%7Bp2%7D%29%281-%5Cfrac%7B1%7D%7Bp3%7D%29....%281-%5Cfrac%7B1%7D%7Bp%20n%7D%29，其中p1，p2.....pn是n的质因子
题目：
https://i-blog.csdnimg.cn/direct/eb078e3b4dbc4ae88c8be36d8ad6df05.png
#include<bits/stdc++.h>
using namespace std;
/*
先试除法分解质因数，在分解过程中如果遇到质因子，那么就用公式计算欧拉函数的结果
*/
int main() {
int n; cin >> n;
while(n--){
int x; cin >> x;
int res = x;
for(int i = 2; i < x / i; i++){
if(x % i == 0){
// 为了除尽，将res * (1 - 1/i) -> res * (i - 1) / i
res = res * (i - 1) / i;
while(x % i == 0) x /= i;
}
}
if(x > 1) res = res * (x - 1) / x;
cout << res << '\n';
}
return 0;
}
筛法求欧拉函数:
求1~n之间全部数的欧拉函数就可以用筛选法
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6+10;
int cnt,prime,phi;
bool st;
ll get_eulers(int n){
phi = 1;
for(int i = 2; i <= n; i++){
if(!st){
//质数
prime = i;
phi = i - 1;
}
// 质数的倍数标记为不是质数
for(int j = 0; prime <= n / i; j++){
st * i] = true;
// Prime是i其中的质因子
if(i % prime == 0){
phi * i] = phi * prime;
break;
}
phi*i] = phi * (prime - 1);
}
}
ll res = 0;
for(int i = 1; i <= n; i++) res += phi;
return res;
}
int main() {
int n; cin >> n;
cout << get_eulers(n) <<'\n';
return 0;
}
https://i-blog.csdnimg.cn/direct/1b8e296766994b39940401aa4d80164d.png
快速幂：
快速幂：
快速幂算法的目标是计算https://latex.csdn.net/eq?a%5E%7Bk%7D%20mod%20p。传统的做法是通过循环将 a 一连乘 k 次，时间复杂度是 O(k)。但快速幂算法利用了二进制体现的特性，将这个过程优化到了 O(logk)
https://i-blog.csdnimg.cn/direct/42820187cba340c083797827c5fd1d48.png
b个数之间我们不难发现规律：每一个数都是前一个数平方%p。
https://i-blog.csdnimg.cn/direct/98bc27d3f74b4abd8e49fb8405961d3b.png
题目：
https://i-blog.csdnimg.cn/direct/dd1decf35057497bbb135f9dbeb2c185.png
#include<bits/stdc++.h>
using namespace std;
int n;
int ksm(int a,int k,int p){
int res = 1;
while(k){
//如果在二进制当中该位是1的话就要累乘到res中
if(k & 1) res = (ll) res * a % p;
k >>= 1;// 相当处理下一位
//每一个数都是前一个数平方%p
a = (ll)a * a % p;
}
return res;
}
int main() {
scanf("%d",&n);
while(n--){
int a,k,p;
scanf("%d %d %d",&a,&k,&p);
printf("%d\n",ksm(a,k,p));
}
return 0;
}
快速幂求逆元：
对于这类题目，其实就是找到一个数x，可以或许使得https://latex.csdn.net/eq?b*x%20%3D%201。
根据费马小定理：https://i-blog.csdnimg.cn/direct/0d45f5d29cc14ddd8d93d08ef3750700.png
我们可以知道对于素数来说，https://latex.csdn.net/eq?a%5E%7Bp-1%7D%20mod%20p%20%3D%201，所以对于a来说https://latex.csdn.net/eq?a*a%5E%7Bp-2%7D%20mod%20p%20%3D%201。
故对于质数a来说，该逆元就是https://latex.csdn.net/eq?a%5E%7Bp-2%7D。
至于无解的环境就是a是p的倍数，此时https://latex.csdn.net/eq?a*a%5E%7Bp-2%7D%20mod%20p%20%3D%200，不可能为1。
题目：
https://i-blog.csdnimg.cn/direct/d073a32c1604462a93527276b2cc7c26.png
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
int ksm(int a,int k,int p){
int res = 1;
while(k){
//如果在二进制当中该位是1的话就要累乘到res中
if(k & 1) res = (ll) res * a % p;
k >>= 1;// 相当处理下一位
//每一个数都是前一个数平方%p
a = (ll)a * a % p;
}
return res;
}
int main() {
scanf("%d",&n);
while(n--){
int a,p;
//如果a是p的倍数那么一定无解
//如果 不是，根据费马定理可以构造出解
scanf("%d %d",&a,&p);
int res = ksm(a,p-2,p);
//p == 2的时候，一定返回的是1
if(a % p) printf("%d\n",res);
else puts("impossible");
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]