欧拉函数:

定义:

互质:互质是公约数只有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....

依次类推合并得到

\phi (n) = n (1-\frac{1}{p1})(1-\frac{1}{p2})(1-\frac{1}{p3})....(1-\frac{1}{p n}),其中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} mod p。传统的做法是通过循环将 a 连续乘 k 次,时间复杂度是 O(k)。但快速幂算法利用了二进制表示的特性,将这个过程优化到了 O(log⁡k)

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,能够使得b*x = 1

根据费马小定理:

我们可以知道对于素数来说,a^{p-1} mod p = 1,所以对于a来说a*a^{p-2} mod p = 1

故对于质数a来说,该逆元就是a^{p-2}

至于无解的情况就是a是p的倍数,此时a*a^{p-2} mod p = 0,不可能为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;
}

 

 

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部