基础数论

作者: 雨落八千里 | 来源:发表于2019-09-26 22:27 被阅读0次

大数取模

       ll ans=0;
       for(int i=0; i<strlen(s); i++)
       {
           ans=(ans*10+s[i]-'0')%mod;
       }

快速幂

计算一个数 $a$ 的 $n$ 次幂即 $a^n$
快速幂的思想就是将指数 $n$ 转化成二进制再进行求解

$eg:a^{11}$
其中指数 $(11)_2=1011$ ,所以我们可以求出 $a^{11}=a^{2^0+2^1+2^3}=a^{1}*a^{2}*a^{8}$ 按照循环要循环 $11$ 次，现在只要计算 $3$ 次,所以快速幂的时间复杂度是 $log(n)$
long long power(int a,int n)
{
   long long ans=1;
   long long base=a;
   while(n)
   {
       if(n&1)
       {
           ans=ans*base;
       }
       base=base*base;
       n>>=1;
   }
   return ans;
}

欧几里得

求最大公约数

long long gcd(long long a,long long b)
{
   if(b==0)
   {
       return a;
   }
   else
   {
       return gcd(b,a%b);
   }
}

最小公倍数 $=a*b/gcd(a,b)$

扩展欧几里得

对于不完全为 $0$ 的非负整数 $a，b，gcd(a，b)$ 表示 $a，b$ 的最大公约数，必然存在整数对 $( x , y )$ , 使得 $ax + by = gcd ( a , b )$ .

证明

①： $b == 0$ 立即推 $=> x = 1 , y = 0 ;$
②： $a\&\&b$
设 $a * x1 + b * y1 = gcd ( a , b ) ;$
设 $b * x2 + ( a \% b ) * y2 = gcd ( b , a \% b ) ;$
已知： $gcd ( a , b ) == gcd ( b , a \% b )$ (欧几里得)
立即推
$=> a * x1 + b * y1 = b * x2 + ( a\% b ) * y2 ;$
$=> a * x1 + b * y1 = b * x2 + ( a – a / b * b ) * y2 ;$
$= a * y2 + b * ( x2 – ( a / b ) * y2 ) ;$
可得： $x1 = y2$ ;
$y1 = x2 – ( a / b ) * y2 ;$
define ll long long
void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
     if(b==0)
     {
           x=1;
           y=0;
           gcd=a;
     }
     else
     {
           exgcd(b,a%b,gcd,y,x);
           y-=x*(a/b);
     }
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
     if(b==0)
     {
           x=1;
           y=0;
           return a;
     }      
     ll r = exgcd(b,a%b,y,x);
     y-=x*(a/b);
     return r;
}

逆元

对于正整数 $a$ ，如果有 $a*x≡1(mod\ \ \ m)$
（即 $a*x\%m==1$ ），那么把这个同余方程中的最小正整数解 $x$ 叫做 $a$ 模 $m$ 的逆元。

逆元用途
如何求解 $(A/B)\%C$ ，取模运算中 $(A/B)\%C!=(A\%C)/(B\%C)$
在这种情况下就要求 $B$ 在模 $C$ 的情况下的逆元 $B^{'}$ 了
即 $(B*B^{'}\%C==1)$ ,
然后 $(A/B)\%C==(A*B^{'})\%C$

逆元求法
①.费马小定理
假如 $m$ 是一个质数且 $gcd(a,m)==1$ 那么 $m^{'}=a^{m-2}$
因为根据费马小定理可知 $a^{m-1}≡1\ (mod\ \ m)$
$a*a^{m-2}≡1\ \ (mod\ \ m)$
所以 $m^{'}=a^{m-2}$
②.扩展欧几里得算法
扩展欧几里得( $a , m$ 互质，且 $m$ 不是质数时也可使用)
求解 $a*x+b*m=1$
解出的最小正整数解 $x$ 叫做 $a$ 模 $m$ 的逆元。
ll inv ( ll a , ll b )
{
   ll gcd, x, y;
   exgcd(a, b, gcd, x, y);
   return gcd == 1 ? ( x % b + b ) % b : -1 ;   // x 可能为负数
}

中国剩余定理
$\begin{cases} x≡a_1\ \ mod\ \ m_1\\ x≡a_2\ \ mod\ \ m_2\\ ...\\ x≡a_n\ \ mod\ \ m_n\\ \end{cases}$
其中 $m_1,m_2,m_3,m_4,...,m_n$ 两两互质的整数

结论：

其中

M=m_1*m_2*....*m_n

t_i=inv(M/m_i,m_i)

M_i=M/m_i

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int mm=1e6+10;
ll c[mm],mod[mm];
ll exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
   if(b==0)
   {
       x=1;
       y=0;
       gcd=a;
   }
   else
   {
       exgcd(b,a%b,gcd,y,x);
       y-=x*(a/b);
   }
}
ll inv(ll a,ll b)
{
   ll gcd,x,y;
   exgcd(a,b,gcd,x,y);
   return gcd==1?(x%b+b)%b:-1;
}
int main( )
{
   int n;
   while(~scanf("%d",&n))
   {

       ll ans=1;
       for(int i=1; i<=n; i++)
       {
           scanf("%lld%lld",&mod[i],&c[i]);
           ans*=mod[i];
       }
       ll sum=0;
       for(int i=1; i<=n; i++)
       {
           ll a=ans/mod[i]; ll b=mod[i];
           sum=(sum+c[i]*a*inv(a,b)%ans)%ans;
       }
       printf("%lld\n",sum);
   }
   return 0;
}

扩展中国剩余定理
$\begin{cases} x≡a_1\ \ mod\ \ m_1\\ x≡a_2\ \ mod\ \ m_2\\ ...\\ x≡a_n\ \ mod\ \ m_n\\ \end{cases}$
其中 $m_1,m_2,m_3,m_4,...,m_n$ 两两不一定互质的整数

$\begin{cases} x≡a_1\ \ mod\ \ m_1\\ x≡a_2\ \ mod\ \ m_2\\ \end{cases}$
$\begin{cases} x=a_1+k_1*m_1\\ x=a_2+k_2*m_2\\ \end{cases}$
$k_1*m_1+(-k_2)*m_2=a_2-a_1$
令 $d=gcd(m_1,m_2),c=a_2-a_1$
根据扩展欧几里得算法求解 $x,y$ ,满足 $x*m_1+y*m_2=d$
则 $x*(c/d)*m_1+y*(c/d)*m_2=d*c/d$
$\begin{cases} k_1=x*(c/d)\\ k_2=-y*(c/d)\\ \end{cases}$
实际上有多组解
$\begin{cases} k_1=x*(c/d)+(m_2/d)*n\\ k_2=-y*(c/d)-(m_1/d)*n\\ \end{cases}\ \ \ \ \ n\in Z$

取 $k_1$ 的最小整数解，
$\begin{cases} ans=a_1+k_1m_1\\ M=lcm(m_1,m_2) =(m_1*m_2)/d\ \ \ \ \ \\ \end{cases}$
最后合成 $x≡ans(mod\ \ M)$

void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
   if(b==0)
   {
       x=1;
       y=0;
       gcd=a;
   }
   else
   {
       exgcd(b,a%b,gcd,y,x);
       y-=x*(a/b);
   }
}
ll mul(ll a,ll n,ll m)//快速乘
{
   ll ans=0;
   ll base=a;
   while(n)
   {
       if(n&1)
       {
           ans=(ans+base)%m;
       }
       base=(base+base)%m;
       n>>=1;
   }
   return ans%m;
}
ll excrt(int n)
{
   ll x,y,gcd;
   ll M=1,ans=0;//k数组是被模数，mod数组是模数，k%mod
   for(int i=1;i<=n;i++)
   {
       ll a=M;
       ll b=mod[i];
       ll c=(k[i]-ans%b+b)%b;
       exgcd(a,b,gcd,x,y);
       if(c%gcd!=0)
       {
           return -1;
       }
       ll t=b/gcd;
       x=mul(x,c/gcd,t);
       ans+=x*M;//更新前i个方程组的答案
       M*=t;//前i个modi的小公倍数
       ans=(ans%M+M)%M;
   }
   return (ans%M+M)%M;
}

P4777 【模板】扩展中国剩余定理（EXCRT）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int MAX=1e5+10;
ll k[MAX],mod[MAX];//mod数组是模数,k数组是被模数-->>k%mod
void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        gcd=a;
    }
    else
    {
        exgcd(b,a%b,gcd,y,x);
        y-=x*(a/b);
    }
}
ll mul(ll a,ll n,ll m)
{
    ll ans=0;
    ll base=a;
    while(n)
    {
        if(n&1)
        {
            ans=(ans+base)%m;
        }
        base=(base+base)%m;
        n>>=1;
    }
    return ans%m;
}
ll excrt(int n)
{
    ll x,y,gcd;
    ll M=1,ans=0;
    for(int i=1; i<=n; i++)
    {
        ll a=M;
        ll b=mod[i];
        ll c=(k[i]-ans%b+b)%b;
        exgcd(a,b,gcd,x,y);
        if(c%gcd!=0)
        {
            return -1;
        }
        ll t=b/gcd;
        x=mul(x,c/gcd,t);
        ans+=x*M;
        M*=t;
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}
int main( )
{
    int n;
    while(~scanf("%d",&n))
    {

        for(int i=1; i<=n; i++)
        {
            scanf("%lld%lld",&mod[i],&k[i]);
        }
        printf("%lld\n",excrt(n));
    }
    return 0;
}

基础数论

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读