跳到主要内容

同余和矩阵乘法

AcWing 203. 同余方程​

题目​

求关于 x 的同余方程 ax≡1(modb) 的最小正整数解。

思路​

扩展欧几里得算法可以求同余方程。 先将原同余方程转化为：ax+by=1ax+by=1,求最小的xx，带入扩展欧几里得算法模版即可。

代码​

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

int exgcd(int a,int b,int &x,int &y){
    if (b==0){
        x=1,y=0;
        return a;
    }
    //这里交换x,y会更加方便
    int d= exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    LL a,b;
    cin>>a>>b;
    int x,y;
    exgcd(a,b,x,y);
    pr((x%b+b)%b)

    return 0;
}

AcWing 222. 青蛙的约会​

题目​

https://www.acwing.com/problem/content/224/ 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。 它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。 可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。 不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。 但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。 为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙 A 和青蛙 B ，并且规定纬度线上东经 0 度处为原点，由东往西为正方向，单位长度 1 米，这样我们就得到了一条首尾相接的数轴。 设青蛙 A 的出发点坐标是 x ，青蛙 B 的出发点坐标是 y 。 青蛙 A 一次能跳 m 米，青蛙 B 一次能跳 n 米，两只青蛙跳一次所花费的时间相同。 纬度线总长 L 米。 现在要你求出它们跳了几次以后才会碰面。

思路​

假设一开始A在B的后面，那么A就需要追B：(b-a)米，而每跳一次，A和B之间的距离可以缩小 (m-n)米，假设一共跳了x次，追了y圈，则(m−n)∗x=b−a+L∗y(m-n) *x=b-a+L*y,则(m−n)∗x−L∗y=b−a(m-n)*x-L*y=b-a，这是一个不定方程，可以用扩展欧几里得算法来求解：

求不定方程ax+by=cax+by=c的一组整数解： 如果gcd(a,b)∣cgcd(a,b)|c,一定有整数解，否则没有 可以先用扩展欧几里得算法求出ax+by=gcd(a,b)ax+by=gcd(a,b)的一组解，在乘以cgcd(a,b)\frac{c}{gcd(a,b)}，即可得到原方程的特解。 通解： {x=x0+bgcd⁡(a,b)∗ky=y0−agcd⁡(a,b)∗k(考虑ax+by=0构造)\left\{\begin{array}{l} x=x_{0}+\frac{b}{\operatorname{gcd}(a, b)} * k \\ y=y_{0}-\frac{a}{\operatorname{gcd}(a, b)} * k \end{array}\right ( 考虑 a x+b y=0 构造 )

在本题中，通过扩展欧几里得算法求出来的xx最后应该再乘上c/dc/d,即(b−a)/d,(b-a)/d,而通解里面的b/db/d应该为L/dL/d

代码​

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b,a%b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    LL x,y,m,n,L,a,b;
    cin>>a>>b>>m>>n>>L;
    LL d= exgcd(m-n,-L,x,y);
    LL c=b-a;
    if (c%d)pr("Impossible")
    else{
        x*=c/d;
        LL t= abs(L/d);
        pr((x%t+t)%t)
    }
    return 0;
}

AcWing 202. 最幸运的数字​

题目​

https://www.acwing.com/problem/content/204/ 8 是中国的幸运数字，如果一个数字的每一位都由 8 构成则该数字被称作是幸运数字。 现在给定一个正整数 L ，请问至少多少个 8 连在一起组成的正整数（即最小幸运数字）是 L 的倍数。

思路​

d∣nd|n表示nn可以整除dd 题目意思为求解满足L可以整除x个8的最小整数x，x个8可以写成8∗1111(x个1)8*1111(x个1) ，x个1又可以写成9999（x个9）9\frac{9999（x个9）}{9},可以写成89(10x−1)\frac{8}{9}(10^x-1)，因此题目可以转换为9L∣8∗(10x−1)9L|8*(10^x-1) ,因为8和9是互质的，设t=(10x−1)t=(10^x-1),则：9L∣8t9L|8t,即9Ld∣8dt\frac{9L}{d}|\frac{8}{d}t

  • 设gcd(L,8)=d,则gcd(9L,8)=d,则gcd(9Ld,8d)=1gcd(L,8)=d,则gcd(9L,8)=d,则gcd(\frac{9L}{d},\frac{8}{d})=1,因此只有tt可以整除9Ld\frac{9L}{d},即9Ld∣t\frac{9L}{d}|t

原式可以化简为：10x≡1( mod 9Ld)10^x\equiv 1(\bmod \frac{9L}{d}) 欧拉定理为：若gcd(a,m)=1gcd(a,m)=1,即a和m互质，则aψ(m)≡1( mod m)a^{\psi(m)} \equiv 1(\bmod m)，但是这里不能保证ψ(m)\psi(m)就是最小的整数解x, 此时又有如下定理：满足上式的最小整数解x一定是ψ(m)\psi(m)的约数

代码​

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

//欧几里得算法
LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

//欧拉函数
LL get_euler(LL c) {
    LL res = c;
    for (int 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 b)
{
    LL res = 0;
    while (k)
    {
        if (k & 1) res = (res + a) % b;
        a = (a + a) % b;
        k >>= 1;
    }
    return res;
}

LL qmi(LL a, LL k, LL b)
{
    LL res = 1;
    while (k)
    {
        if (k & 1) res = qmul(res, a, b);
        a = qmul(a, a, b);
        k >>= 1;
    }
    return res;
}

int main() {
//    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int t=0;
    LL L;
    while (cin >> L, L) {
        LL d = gcd(L, 8);
        LL c = 9 * L / d;
        LL phi = get_euler(c);
        LL res = 1e18;
        if (c % 2 == 0 || c % 5 == 0) res = 0;
        else {
            for (LL i = 1; i <= phi / i; i++) {
                if (phi % i == 0) {
                    if (qmi(10,i,c)==1) res= min(res,i);
                    if (qmi(10,phi/i,c)==1) res= min(res,phi/i);
                }
            }
        }
        printf("Case %d: %lld\n",++t,res);
    }

    return 0;
}

AcWing 1298. 曹冲养猪​

题目​

自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲很不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。 举个例子，假如有 16 头母猪，如果建了 3 个猪圈，剩下 1 头猪就没有地方安家了；如果建造了 5 个猪圈，但是仍然有 1 头猪没有地方去；如果建造了 7 个猪圈，还有 2 头没有地方去。 你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

思路​

中国剩余定理：

中国剩余定理可以用来求解下面的线性同余方程组 {x≡r1( mod m1)x≡r2( mod m2)⋮x≡rn( mod mn)\left\{\begin{array}{c} x \equiv r_{1}\left(\bmod m_{1}\right) \\ x \equiv r_{2}\left(\bmod m_{2}\right) \\ \vdots \\ x \equiv r_{n}\left(\bmod m_{n}\right) \end{array}\right. 其中模数m1,m2,⋯ ,mn为两两互质的整数,求x的最小非负整数解。其中模数 m_{1}, m_{2}, \cdots, m_{n} 为两两互质的整数, 求 x 的最小非负整数解。 做法如下：

  1. 计算所有的模数的积为M
  2. 计算第i个方程的ci=Mmic_i=\frac{M}{m_i}
  3. 求cic_i再模mim_i下的逆元ci−1c_i^{-1}
  4. x=∑i=1nricici−1( mod M)x=\sum_{i=1}^{n}{r_ic_ic_i^{-1}}(\bmod M)

乘法逆元：

当aa与mm互质时，对于方程ax≡1( mod m)ax\equiv 1(\bmod m)求aa当乘法逆元x(0<x<m)x(0<x<m) 做法：

  1. 将方程变形为：ax+my=1ax+my=1
  2. 使用扩展欧几里得算法求ax+my=gcd(a,m)ax+my=gcd(a,m)的一组解xx，
  3. 原方程的解为：(x%m+m)%m(x \% m+m) \% m

代码​

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

int r[N],m[N];
int n;

LL exgcd(LL a,LL b,LL &x,LL &y){
    if (b==0){
        x=1,y=0;
        return a;
    }
    LL d= exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    cin>>n;
    LL M=1;
    for(int i=1;i<=n;i++) {
        cin >> m[i] >> r[i];
        M*=m[i];
    }
    LL res=0;
    for(int i=1;i<=n;i++){
        LL mi=M/m[i],x,y;
        exgcd(mi,m[i],x,y);
        res=(res+r[i]*mi*x);
    }
    pr((res%M+M)%M)

    return 0;
}


AcWing 1303. 斐波那契前 n 项和​

题目​

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n−1}+f_{n−2}。 现在问题很简单，输入 nn 和 mm ，求 fnf_n 的前 nn 项和 Sn mod mS_n\bmod m 。

思路​

image-20240818225814035

latex无法渲染：

$\begin{bmatrix}
f_n & f_{n+1} &S_n
\end{bmatrix}*\begin{bmatrix}
0 &1 &0 \\
1 & 1 & 1\\
0& 0&1
\end{bmatrix}
=
\begin{bmatrix}
f_{n+1} & f_{n+2} &S_{n+1}
\end{bmatrix}$,设$A=\begin{bmatrix}
0 &1 &0 \\
1 & 1 & 1\\
0& 0&1
\end{bmatrix}$
即$F_{n+1}=F_n*A$，则$F_n=F_1*A^{n-1}$

代码​

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 3;

int n,m;

void mul(int res[],int a[],int b[][N]){
    int temp[N]={0};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            temp[i]=(temp[i]+(ll) a[j]*b[j][i])%m;
        }
    }
    memcpy(res,temp,sizeof temp);
}

void mul(int res[][N],int a[][N],int b[][N]){
    int temp[N][N]={0};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                temp[i][j]=(temp[i][j]+(ll) a[i][k]*b[k][j] )%m;
            }
        }
    }
    ::memcpy(res,temp,sizeof temp);
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    cin>>n>>m;
    int f1[N]={1,1,1};
    int a[N][N]={
            {0,1,0},
            {1,1,1},
            {0,0,1}
    };
    n--;
    //fn=f1*A^(n-1)
    while (n){
        if (n&1) mul(f1,f1,a);//一维*二维
        mul(a,a,a);//二维*二维
        n>>=1;
    }
    pr(f1[2])
    return 0;
}

0%