2021-03-09-数论

参考链接

乘法逆元 扩展欧几里得定理 欧拉函数推导 欧拉函数代码 欧拉函数详细推导 中国剩余定理

扩展欧几里得算法求逆元

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll& x,ll& y) ///后两个参数为引用
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll gcd_ans=exgcd(b,a%b,x,y);
    ll tem=x;
    x=y;
    y=tem-a/b*y;
    return gcd_ans;
}
int main()
{
    cout<<"请输入a和q的值"<<endl;
    ll a,q,x=0,y=0;
    cin>>a>>q;
    ll gcd_ans=exgcd(q,a,x,y);
    ll mul=q/gcd_ans;
    y=(y%mul+mul)%mul;
    cout<<"a关于模q的逆元为"<<y<<endl;
}

扩展欧几里得算法还有其他应用，例如求解同余方程，其余请参考扩展欧几里得定理博客。

费马小定理求解逆元

只适用于q为质数时，可以求解逆元。 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,q;
ll ksm(ll n,ll k)
{
    ll sum1=1,sum2=n;
    while(k!=0)
    {
        if(k%2==1)
            sum1=sum1*sum2%q;
        sum2=sum2*sum2%q;
        k/=2;
    }
    return sum1;
}
int main()
{
    cout<<"请输入a和q的值"<<endl;
    cin>>a>>q;
    cout<<"a关于模q的逆元为"<<ksm(a,q-2)<<endl;
}

费马小定理乘法逆元一个应用便是求组合数，一般对1e9+7进行取余，而1e9+7是一个质数，可以用小费马定理来求逆元，代码为：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll jc[100500]={0};
ll ny[100500]={0};
ll ksm(ll n,ll k)
{
    ll sum1=1,sum2=n;
    while(k!=0)
    {
        if(k%2==1)
            sum1=sum1*sum2%mod;
        sum2=sum2*sum2%mod;
        k/=2;
    }
    return sum1;
}
ll c(ll n,ll m)
{
    if(n<m)
        swap(n,m);
    return (jc[n]%mod*ny[m]%mod)%mod*ny[n-m]%mod;
}
int main()
{
    jc[0]=1;
    for(int i=1;i<=100000;i++)
    {
        jc[i]=jc[i-1]*i;
        ny[i]=ksm(jc[i],mod-2);
    }
    int n,m;
    cin>>n>>m;
    cout<<c(n,m)<<endl;
}

欧拉函数

欧拉函数用来求比n小且和n互质元素个数。 代码

#include <bits/stdc++.h>
using namespace std;
int is_prime[100500]={0};
vector<int>prime;
int oula_table[100500]={0};
void init(int n)  ///打素数表
{
    for(int i=2;i<=n;i++)
    {
        if(!is_prime[i])
            prime.push_back(i);
        for (int j = 0; j <=prime.size() && i*prime[j] <= n; j++) {
            is_prime[i*prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}
int oula1(int n) ///根据素数表求解欧拉函数
{
    int ans=n;
    for(int i=0;prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]==0)
            ans=ans-ans/prime[i];
        while(n%prime[i]==0)
            n/=prime[i];
    }
    return ans;
}
int oula2(int n)  ///分解质因数法求解欧拉函数
{
    int m=n;
    int ans=n;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(m%i==0)
            ans=ans-ans/i;
        while(m%i==0)
            m/=i;
    }
    if(m!=1)
        ans=ans-ans/m;
    return ans;
}
void get_oula_table(int n) ///欧拉打表
{
    for(int i=1;i<=n;i++)
        oula_table[i]=0;
    oula_table[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!oula_table[i]) ///说明i是质数
        {
            for(int j=i;j<=n;j+=i) //去找i的倍数
            {
                if(!oula_table[j])
                    oula_table[j]=j;
                oula_table[j]=oula_table[j]/i*(i-1);
            }
        }
    }
}
int main()
{
    int n;
    cin>>n;
    init(n);
    cout<<"找素数求解欧拉函数值为"<<oula1(n)<<endl;
    cout<<"分解质因数法求解欧拉函数值为"<<oula2(n)<<endl;
    get_oula_table(n);
    cout<<"打表法求解欧拉函数值为";
    for(int i=1;i<=n;i++)
        cout<<oula_table[i]<<' ';
}

欧拉函数的应用 边塞任务 你的要塞⾥有N名随从，每名随从有⼀个战⽃⼒值Ai，不同随从的战⽃⼒可以相同，且永远不超过N。⼀个要塞任务需要恰好M个随从参与。 要塞任务的奖励取决于随从们配合的程度。（显⽽易见地），M个随从的联合战⽃⼒A为它们战⽃⼒的最⼤公约数，⽽任务的奖励分数定义为ϕ(A)。 求最⼤可能的奖励分数。 输入 本题有多组数据，第⼀⾏为数据组数T（T≤10）。 接下来每组数据有两⾏，第⼀⾏两个整数N，M，第⼆⾏N个整数Ai（N，M，Ai≤100000）。 输出 最多的奖励分数。 样例输入

1
5 2
1 4 6 9 12

样例输出

2

提示 样例解释：派出编号为6和12的随从，联合战⽃⼒为3，奖励分数2。 代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
typedef long long int ll;
int pd[100500] = { 0 };//01数组存放是否为质数
int b[100500] = { 0 };//存放的质数数列
int out[100500] = { 0 };//欧拉函数 φ(A)
int num[100500] = { 0 };//计数用的
void init()
{
    //欧拉筛法
    int sum = 0;
    for (int i = 2; i <= N; i++)
    {
        if (!pd[i])
        {
            b[++sum] = i;
            out[i] = i - 1;
        }
        for (int j = 1; b[j] * i <= N; j++)
        {
            pd[b[j] * i] = 1;
            if (i % b[j] == 0)
                break;
        }
    }
    //求φ(A)
    out[1] = 1;
    int t;
    for (int i = 2; i <= N; i++)
    {
        if (pd[i])
        {
            out[i] = i;
            t = i;
            for (int j = 1; j <= sum && t > 1; j++)
            {
                if (i % b[j] == 0)
                {
                    out[i] = out[i] * (b[j] - 1) / b[j];        //套用公式
                    while (t % b[j] == 0)
                    {
                        t = t / b[j];
                    }
                }
                if (b[j] * 2 > i)    
                    break;
            }
        }
    }
}
int main()
{
    init();
    int t;
    scanf("%d", &t);
    for (int k1= 0; k1 < t; k1++)
    {
        int n, k;
        int ans = -1;
        memset(num, 0, sizeof(num));    //清空，勿忘@！！！
        scanf("%d%d", &n, &k);
        ll max1 = -1;
        for (int i = 0; i < n; i++)
        {
            ll x;
            scanf("%lld", &x);
            num[x]++;                   //计数
            max1 = max(max1, x);
        }
        for (int i = 1; i <= max1; i++)
        {
            ll tot = 0;
            for (int j = i; j <= max1; j = j + i)//j每一次递增i则这些数肯定有一个公约数i
            {
                tot += num[j];                  //计数
            }
            if (tot >= k)//如果数目大于k
            {
                ans = max(ans, out[i]);         //计算 φ(A) 并求最大值
            }
        }
        cout << ans << endl;
    }
    return 0;
}