欧拉函数:
定义:
互质:互质是公约数只有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....
依次类推合并得到
,其中p1,p2.....pn是n的质因子
题目:
- #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[N],phi[N];
- bool st[N];
- ll get_eulers(int n){
- phi[1] = 1;
- for(int i = 2; i <= n; i++){
- if(!st[i]){
- //质数
- prime[cnt++] = i;
- phi[i] = i - 1;
- }
- // 质数的倍数标记为不是质数
- for(int j = 0; prime[j] <= n / i; j++){
- st[prime[j] * i] = true;
- // Prime[j]是i其中的质因子
- if(i % prime[j] == 0){
- phi[prime[j] * i] = phi[i] * prime[j];
- break;
- }
- phi[prime[j]*i] = phi[i] * (prime[j] - 1);
- }
- }
- ll res = 0;
- for(int i = 1; i <= n; i++) res += phi[i];
- return res;
- }
- int main() {
- int n; cin >> n;
- cout << get_eulers(n) <<'\n';
- return 0;
- }
复制代码
快速幂:
快速幂:
快速幂算法的目标是计算。传统的做法是通过循环将 a 一连乘 k 次,时间复杂度是 O(k)。但快速幂算法利用了二进制体现的特性,将这个过程优化到了 O(logk)
b个数之间我们不难发现规律:每一个数都是前一个数平方%p。
题目:
- #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,可以或许使得。
根据费马小定理:
我们可以知道对于素数来说,,所以对于a来说。
故对于质数a来说,该逆元就是。
至于无解的环境就是a是p的倍数,此时,不可能为1。
题目:
- #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企服之家,中国第一个企服评测及商务社交产业平台。 |