同余和矩阵乘法

同余：扩展欧几里得算法

已知GCD(a,b)=d

可求a*x+b*y=d x和y是要求的

大致的问题 a*x同余b(mod c)等价于a*x+c*y=b

模板

int exgcd(int a,int b,int &x,int &y)//拓展欧几里得求ax+by=d的方程
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

---

1.同余方程

203. 同余方程 - AcWing题库

ax=1(mod b)转化为ax+by=1，则直接用拓展欧几里得算法即可求x,y，最小x解为x0%b

#include 
using namespace std;
typedef long long ll;
int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    int a,b;
    cin>>a>>b;
    int x,y;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b<
    return 0;
}

2.青蛙的约会

222. 青蛙的约会 - AcWing题库

然后用扩展欧几里得算法就可以得到任意一组解 然后是求x的最小解 并且x是不等于0 的

则最小的x为x0%(l/d)

#include
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)//拓展欧几里得求ax+by=d的方程
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
   ll a,b,n,m,l;
   cin>>a>>b>>m>>n>>l;
   ll x,y;
   ll d=exgcd(m-n,l,x,y);
   if((b-a)%d) puts("Impossible");//假如b-a不是公约数
   else
   {
       x*=(b-a)/d;//将x扩大相应的倍数
       ll t=abs(l/d);//将d除过来，让右边为1，才能用t0%b为最小这个定里
       cout<<((x%t)+t)%t<//输出最小结果
   }
    return 0;
}

 3.最幸运的数字

202. 最幸运的数字 - AcWing题库

#include
using namespace std;
typedef long long ll;
ll get_euler(ll c)//获取一个数的欧拉数
{
    ll res=c;
    for(ll i=2;i<=c/i;i++)
        if(c%i==0)
        {
            while(c%i==0) c/=i;
            res=res/i*(i-1);//套欧拉函数的公式
        }
    if(c>1) res=res/c*(c-1);
    return res;
}
ll qmul(ll a,ll k,ll p)//龟速乘
{
    ll res=0;
    while(k)
    {
        if(k&1) res=(res+a)%p;
        a=(a+a)%p;
        k>>=1;
    }
    return res;
}
ll qmi(ll a,ll k,ll p)//快速幂
{
    ll res=1;
    while(k)
    {
        //res=(__int128_t)res*a%p也行
        if(k&1) res=qmul(res,a,p);//因为乘法会爆ll,所以用龟速乘
        //a=(__int128_t)a*a%p也行
        a=qmul(a,a,p);//因为乘法会爆ll,所以用龟速乘
        k>>=1;
    }
    return res;
}
int main()
{
   int T=1;
   ll l;
   while(cin>>l,l)
   {
       int d=1;
       while(l%(d*2)==0&&d*2<=8) d*=2;
       ll c=9*l/d;//获取要整除的C
       ll phi=get_euler(c);//获取他的欧拉数
       ll res=1e18;
       if(c%2==0||c%5==0) res=0;//假如跟10不互质，则没答案
       for(ll d=1;d*d<=phi;d++)//枚举欧拉数的所有约数
            if(phi%d==0)//假如这个是约数了
            {
               if(qmi(10,d,c)==1) res=min(res,d);//判断符不符合条件
               if(qmi(10,phi/d,c)==1) res=min(res,phi/d);//判断符不符合条件
            }
     printf("Case %d: %lld\n",T++,res);
   }
    return 0;
}

 4.曹冲养猪

信息学奥赛一本通（C++版）在线评测系统

中国剩余定理

#include
using namespace std;
typedef long long ll;
const int N=11;
int A[N],B[N];
int n;
ll exgcd(ll a,ll b,ll &x,ll &y)//用扩展欧几里得求逆元
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
   cin>>n;
   ll M=1,res=0;
   for(int i=0;i
   {
       scanf("%d%d",&A[i],&B[i]);
       M*=A[i];//处理所有的乘积
   }
   for(int i=0;i
   {
       ll Mi=M/A[i];//获取Mi
       ll ti,x;
       exgcd(Mi,A[i],ti,x);//求Mi的逆元ti
       res+=B[i]*Mi*ti;//图片中有讲答案加上即可
   }
   cout<<((res%M)+M)%M<//输出正的模余数
    return 0;
}

 矩阵乘法

1.斐波那契前 n 项和

1303. 斐波那契前 n 项和 - AcWing题库

这里也可以定义为Fn=[fn-1,fn]

详细 

#include
using namespace std;
typedef long long ll;
const int N=3;
int n,m;
void mul(int c[],int a[],int b[][N])
{
    int temp[N]={0};
    for(int i=0;i//矩阵乘法
        for(int j=0;j
          temp[i]=(temp[i]+(ll)a[j]*b[j][i])%m;
    memcpy(c,temp,sizeof temp);
}
void mul(int c[][N],int a[][N],int b[][N])
{
    int temp[N][N]={0};
    for(int i=0;i//矩阵乘法
        for(int j=0;j
          for(int k=0;k
              temp[i][j]=(temp[i][j]+(ll)a[i][k]*b[k][j])%m;
    memcpy(c,temp,sizeof temp);
}
int main()
{
   cin>>n>>m;
   int f1[N]={1,1,1};//f1为1时的矩阵
   int a[N][N]={
    {0,1,0},
    {1,1,1},
    {0,0,1}
   };//a矩阵
   n--;//求Fn-1
   while(n)
   {
       if(n&1) mul(f1,f1,a);//res=res*a
       mul(a,a,a);//a=a*a;
       n>>=1;
   }
   cout<2]<//输出Fn-1的中的f(n-1)+1=fn
    return 0;
}