9.19 第二次作业

第二次作业

7.手动计算（不知道是应该写在纸上照片拍上来还是应该用md写）

(a).

下一步是

此时，那么就可以得到,那么 的乘法逆元就是-2；

(b).

同上易得：

可得的乘法逆元是28；

(c).

可得的乘法逆元是81。

根据书后的解释，将模指数进行分治计算，再将每一部分计算结果乘起来，再用乘积取模，将这一思路用C++表示出来如下：

#include<bits/stdc++.h>
using namespace std;

int Modular(int x,int y,int m)
{
    int a[1000];
    int i=0;
    int n;
    while(1)//将整数转换为二进制数
    {
        if(y>1)
        {
            a[i]=y%2;
            y=y/2;
            i++;
        }
        if(y==0||y==1)
        {
            a[i]=y;
            break;
        }
    }
    int modular=1;
    int t,r,mode;
    while(i>=0)
    {
       if(a[i]==1)//进行分治运算，二进制字节满足1的进行有效运算
       {

           t=pow(2,i);
           n=pow(x,t);
           mode=n%m;
           modular=modular*mode;//将运算结果乘起来
       }
       i--;
    }
    return modular%m;//用乘积再取一次模
}
int main()
{
    int x,y,m;
    int modular;
    cin>>x>>y>>m;
    modular=Modular(x,y,m);
    cout<<modular<<endl;
    return 0;
}

可以看得出来这就是我们熟知的快速幂运算。

由公式可得：（翻了好久线代……）

那么问题就变成了对矩阵的快速幂问题了

def multi(a, b):  # 计算二阶矩阵的相乘
    c = [[0, 0], [0, 0]]  # 定义一个空的二阶矩阵
    for i in range(2):
        for j in range(2):
            for k in range(2):  # 新二阶矩阵的值计算
                c[i][j] = c[i][j] + a[i][k] * b[k][j]
    return c


def matrix(n):
    base = [[1, 1], [1, 0]]  # 元矩阵，这里可以把元矩阵看做是2**0=1
    ans = [[1, 0], [0, 1]]  # 结果矩阵  最开始的结果矩阵也可以看做是1，因为这个矩阵和任意二阶A矩阵相乘结果都是A
    while n:
        if n & 1:  # 取n的二进制的最后一位和1做与运算，如果最后一位是1，则进入if体内部
            ans = multi(ans, base)  # 如果在该位置n的二进制为1，则计算ans和base矩阵
        base = multi(base, base)  # base矩阵相乘，相当于初始base矩阵的幂*2
        n >>= 1  # n的二进制往右移一位
    return ans[0][1]  # 最后获取到的二阶矩阵的[0][1]即f(n)的值
n=int(input(">>>"))
print("Matrix:",matrix(n))

这个也算是经典问题了

那么下面再给出用C编写的版本：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define mod 10000
struct Matrix
        {
    long long ma[2][2];//用结构体表示矩阵
        };
Matrix mul(Matrix A,Matrix B)
{
    Matrix C;
    C.ma[0][0]=C.ma[0][1]=C.ma[1][0]=C.ma[1][1]=0;//用中间变量矩阵C来储存运算结果
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
            {
                C.ma[i][j]=(C.ma[i][j]+A.ma[i][k]*B.ma[k][j])%mod;//矩阵相乘
            }
        }
    }
    return C;
}
Matrix pow_mod(Matrix A,long long n)
{
    Matrix B;
    B.ma[0][0]=B.ma[1][1]=1;//化为单位矩阵
    B.ma[0][1]=B.ma[1][0]=0;
    while(n)
    {
        if(n&1) B=mul(B,A);//进行幂的操作
        A=mul(A,A);
        n>>=1;//二进制数n右移一位
    }
    return B;
}
int main()
{
    long long n;
    while(~scanf("%lld",&n)&&n!=-1)
    {
        Matrix A;
        A.ma[0][0]=1;A.ma[0][1]=1;//斐波那契数列的目标矩阵
        A.ma[1][0]=1;A.ma[1][1]=0;
        Matrix ans=pow_mod(A,n);
        printf("%lld\n",ans.ma[0][1]);//由公式可知，如果运行n次的话，第一列第二行的结果就是F(n)
    }
    return 0;
}

假设和是的逆元，则。

由定理可得：，又因为，所以，即。

说明和是唯一的逆元，与假设矛盾。

综上所述，对于两个互素的和，满足，那么模的逆元是唯一的。

已知整数、，扩展欧几里得算法可以在求得、的最大公约数的同时，能找到整数、（其中一个很可能是负数），使它们满足贝祖等式

如果a是负数，可以把问题转化成。

def ext_gcd(a, b):   #扩展欧几里得算法
    if b == 0:
        return 1, 0, a
    else:
        x, y, gcd = ext_gcd(b, a % b)   #递归直至余数等于0(需多递归一层用来判断)
        x, y = y, (x - (a // b) * y)   #辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立
        return x, y, gcd

那么返回值就是所求逆元。