精华内容
下载资源
问答
  • 题目 给定n组数据ai,bi,mi,对于每组数求出一个xi,使其满足ai∗xi≡bi(modmi),如果无解则输出impossible。 输入格式 第一行包含整数n。 接下来n行,每行包含一组数据ai,bi,mi。...输出共n行,每组数据输出一个...

    题目

    给定n组数据ai,bi,mi,对于每组数求出一个xi,使其满足ai∗xi≡bi(mod mi),如果无解则输出impossible。

    输入格式

    第一行包含整数n。

    接下来n行,每行包含一组数据ai,bi,mi。

    输出格式

    输出共n行,每组数据输出一个整数表示一个满足条件的xi,如果无解则输出impossible。

    每组数据结果占一行,结果可能不唯一,输出任意一个满足条件的结果均可。

    输出答案必须在int范围之内。

    数据范围

    1≤n≤10^5
    1≤ai,bi,mi≤2∗10^9

    输入样例:

    2
    2 3 6
    4 3 5
    

    输出样例:

    impossible
    7

    代码

    n = int(input())
    x, y = 1, 0
    
    def exgcd(a, b):
        global x, y
        if b == 0:
            x, y = 1, 0
            return a
        d = exgcd(b, a % b)
        x, y = y, x
        y -= (a // b) * x
        return d
    
    for _ in range(n):
        a, b, m = map(int, input().split())
        d = exgcd(a, m)
        if b % d != 0: print('impossible')
        else: print(x*(b//d) % m)

     

    展开全文
  • 同余》中等01 —— LeetCode 189. 旋转数组

    🙉饭不食,水不饮,题必须刷🙉

    C语言免费动漫教程,和我一起打卡!
    🌞《光天化日学C语言》🌞

    LeetCode 太难?先看简单题!
    🧡《C语言入门100例》🧡

    数据结构难?不存在的!
    🌳《数据结构入门》🌳

    LeetCode 太简单?算法学起来!
    🌌《夜深人静写算法》🌌

    一、题目

    1、题目描述

    给定一个 n ( n ≤ 1 0 5 ) n(n \le 10^5) n(n105) 个元素的数组,将数组中的元素向右移动 k ( k ≤ 1 0 5 ) k(k \le 10^5) k(k105) 个位置。
      样例输入: n u m s = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] , k = 3 nums = [1,2,3,4,5,6,7], k = 3 nums=[1,2,3,4,5,6,7],k=3
      样例输出: [ 5 , 6 , 7 , 1 , 2 , 3 , 4 ] [5,6,7,1,2,3,4] [5,6,7,1,2,3,4]

    2、基础框架

    • c++ 版本给出的基础框架代码如下:
    class Solution {
    public:
        void rotate(vector<int>& nums, int k) {
        }
    };
    
    • 要求将数组vector<int>& nums原地右移 k k k 个单位。

    3、原题链接

    LeetCode 189. 旋转数组

    二、解题报告

    1、思路分析

      要求原地旋转,我们不妨拷贝一份数组。就会发现,原数组和旋转后数组的位置差了 k k k 个单位,其实这正是数论中同余的概念。
      只不过,这里是下标同余,假设要求的数组为 a,原数组为 pre,则有: a[i] = pre[i - k],但是数组下标不能为负数,所以需要对数组长度取模,令数组长度为 n,则有 a[i] = pre[(i - k) % n];但是在C语言中,负数对正数取模,还是负数,所以需要进行如下处理:a[i] = pre[((i - k) % n + n) % n]

    2、时间复杂度

    • 两个循环都是 O ( n ) O(n) O(n) 的,所以总的时间复杂度就是 O ( n ) O(n) O(n)

    3、代码详解

    #define F(a,b) for(int i = a; i < b; ++i)                  // (1)
    class Solution {
    public:
        void rotate(vector<int>& nums, int k) {
            vector<int> tmp;
            int n = nums.size();
            F(0,n) tmp.push_back(nums[i]);                     // (2)            
            F(0,n) nums[i] = tmp[ ((i - k) % n + n) % n ];     // (3)
        }
    };
    
    • ( 1 ) (1) (1) 用宏定义简化代码;
    • ( 2 ) (2) (2) 引入中介数组tmp
    • ( 3 ) (3) (3) 利用下标同余实现旋转;

    三、本题小知识

    一个数 a a a b b b,要让结果为正数,需要做如下处理:((a % b) + b) % b


    展开全文
  • 最近在做帧同步的实时对战,要自己接管随机数的产生,所以看了一下随机数生成的相关算法。因为游戏会跑在不同平台(iOS/Android)及不同硬件上,所以使用的算法有...这篇博客主要记录关于这个线性同余算法产生随机数的...

    最近在做帧同步的实时对战,要自己接管随机数的产生,所以看了一下随机数生成的相关算法。因为游戏会跑在不同平台(iOS/Android)及不同硬件上,所以使用的算法有以下的要求:1. 不能依赖系统;2. 不能依赖硬件;3. 计算中不能使用浮点数(不同平台不同硬件有可能结果不同)。再结合效率方面的考虑,最终选择采用了线性同余算法,并在基础上做了一定的加强。这篇博客主要记录关于这个线性同余算法产生随机数的一些思考。

    首先要搞清楚随机数的定义,真正的随机数都不是计算出来的,这里我们说的随机数其实都是伪随机数,随机数伪随机数的定义,具体的论证等资料可以自行查阅。产生伪随机数的算法有很多种,线性同余算法基于整数的加、乘和求模,算法简单但是具有较强的规律性与周期性。怎么在这个基础上尽量降低规律性与周期性,使得在更广范围内覆盖更多可能就是我们的目标。

    首先要了解的是线性同余函数公式1d3c28015d36dbad069f1cf555ca8de2.png,最终结果受乘数λ,加数C和模数M决定。M通常我们会使用一个较大的素数,而λ,C的选取在很大程度上会影响生成的随机数的质量。我们尝试使用不同的λ与C去生成一系列的随机数并观察他们。为了直观感受一些列的随机数是否足够随机,我们用这些数字作为X,Y填充一张1024 * 512的位图,观察图上的点的位置,可以得知这一系列随机数在1024 * 512范围内随机分布的情况。

    使用最基础的线性同余公式生成的随机数,因乘数λ、加数C参数不同,有的时候比较随机(图一),有的时候呈现出比较强的规律性(图二),但周期性都是十分短。在多次尝试中能成功填充的点从几千到几万个,但并不能完全填充整张图,证明周期性在1024*512种组合中都无法确保不重复。这样的随机数算法显然是不够好的。要在线性同余算法的基础上加强,首先想到的是计算Xn时,不再只用Xn-1参与,而是用X1到Xn-1的加和。

    使用加和版本的线性同余算法,套用不同的参数λ、C再次生成随机数填充位图观察:

    可以看出加和版本的线性同余算法产生的随机数,因乘数λ、加数C参数不同,有的时候呈现出比较强的规律性(图三),有的时候比较随机(图四)。数量上从10w到50w不等,大部分情况无法覆盖1024*512种情况,极少数情况下能完全覆盖。选取一组较好的λ,C参数,使用加和版本的线性同余算法产生的随机数其实已经可以满足游戏功能的需求了,如果还想加再优化,则要从参数λ,C的变化入手。

    在多次测量的过程中,用不同的参数λ,C能得出不同的表现,那只要λ,C不再取固定值,就相当于混合了使用多个加和线性同余算法生成结果的混合来做随机数。这样做即使一组λ,C生成的随机数有一定的周期性与规律性,但混用多组结果,就能把周期性与规律性再次降低(但无法消除)。

    那么如何给λ,C动态取值呢。方法有两种:

    第一种是预先生成一张素数表,让λ,C在这张表中循环取值,这种方式λ,C之间没有规律性(素数性质),但周期性的大小就取决于这张素数表的大小,通常而言不会有太多组变化,预生成的表最多也就是几百个。

    第二种方式就是λ,C也动态计算得出。这样做其实问题就回到最初的原点,如何使用代码动态生成随机数然后尽量让这些数字的规律性与周期性尽量低。通过上面的分析已经知道,如果λ,C也使用代码生成的话,在周期性上比方法一有更大的优势(选取较好的λ,C可以在1024*512区间内就有几十万种组合,参考图四),但规律性上没有方法一好。

    无论是采用方法一还是方法二,本质上都是在混用多个(有限个)线性同余公式的结果,所以一定还是会有周期性与规律性的问题。方法一优势在于规律性非常低,但素数表的大小决定了周期性大小,通常做不到太多变化,而且占用内存。方法二λ,C组合非常多,不需要额外内存,但要额外计算,并且这些λ,C是会有一定的规律性的,优势是周期性非常长,但规律性上没有方法一好的。

    其实对于游戏逻辑而言,采用固定λ,C的加和线性同模产生的随机数已经足够了,效率还会比较高。但如果想做一个质量很高的随机数生成器,个人建议是采用方法一,然后预先打出一万以内的素数作为λ,C组合使用,这样的λ,C组合已经有上百万种了,混用一百万个加和版本的线性同余算法来生成随机数的话,规律性与随机性方面应该都能满足计算机领域的使用了。

    最后有几点值得注意的是:

    一、计算时使用int或int64,有符号或无符号,对于随机数的生成都会有很大影响,计算时要注意

    二、如果λ,C 较小而M 非常大,在初期会出现连续的递增情况,这三个参数的选取要注意。

    展开全文
  • 同余理论在软件编程中的应用.pdf设计通讯 2oo7 No.2同余理论在软件编程中的应用石军摘 要 简要介绍同余理论的概念、性质、四则运算等基本知识,通过几个...关键词 同余 算法 校验码 计算机应用1.3 同余式的性质0...

    同余理论在软件编程中的应用.pdf

    设计通讯 2oo7 No.2

    同余理论在软件编程中的应用

    石军

    摘 要 简要介绍同余理论的概念、性质、四则运算等基本知识,通过几个实际应用来说明同余理论在软

    件编程中的重要性及实用性。

    关键词 同余 算法 校验码 计算机应用

    1.3 同余式的性质

    0 引 言 同余式和等式一样,都是一种等价关系,即具

    有以下三种性质:

    数学是基础科学,各种数学理论在不同的学科 (1)自反性a;a(mod m);

    中有着广泛的应用。毫无例外,数学理论在软件编 (2)对称性a;b(mod m)0ba(mod m);

    程中更是显得尤为重要。同余理论是数学的一个 (3)传递性a三b(mod m),b;C(mod m)c=>a

    --

    --

    重要分支一一初等数论的核心内容。它在计算机 --c(rood m)。

    软件编程中可以起到优化算法等重要作用。 1.4 同余式的四则运算

    同余式可以相加、相减、相乘:若a;b(mod

    1 同余理论的基本知识 m),C;d(mod m),则a+C;b+d(mod m),a—c

    ;b—d(mod m),ac;bd(rood m);

    同余理论是研究整数性质的数学理论。如果

    展开全文
  • 线性同余方程(C++实现)扩展欧几里得算法求解线性同余方程1. 题目2. 读题(需要重点注意的东西)3. 解法4. 可能有帮助的前置习题5. 所用到的数据结构与算法思想6. 总结 1. 题目 2. 读题(需要重点注意的东西) ...
  • 线性余方法(LCG)是个产生伪随机数的方法。它是根据递归公式:其中是产生器设定的常数...线性同余算法有m 、a 、c 和X0 4个参数,通过置Xn + 1 ≡aXn + c (mod m) ,求得随机数序列< Xn > , 这个序列称作线性...
  • 一、同余模定理 a,b两个数对n取余,余数相同则a和b同余。 如1 mod 5 = 1,6 mod 5=1;则1和6模5同余 二、应用——消除爆int的问题 题目:求解(2^0 + 2^1 + 2^2 +…+ 2^n)%2333 当n足够大时,超出了int的范围。 #...
  • x,yx,yx,y可用扩展欧几里得算法求出。 扩展欧几里得: 由欧几里得算法得 gcd⁡(a,b)=gcd⁡(b,a%b)\gcd(a,b)=\gcd(b,a\%b)gcd(a,b)=gcd(b,a%b) 由裴蜀定理 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b) 当b=0b=0b=...
  • 同余方程

    万次阅读 2021-02-28 22:56:47
    求关于x 的同余方程ax ≡ 1 (mod b)的最小正整数解。 输入描述: 输入只有一行,包含两个正整数a,b,用一个空格隔开。 输出描述: 输出只有一行,包含一个正整数x0,即最小正整数解。输入数据保证一定有解。 示例1 ...
  • ①. 题目 ②. 思路 ③. 学习点 ④. 代码实现
  • 孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物...
  • 本文实例讲述了Python实现的中国剩余定理算法。分享给大家供大家参考,具体如下:中国剩余定理(Chinese Remainder Theorem-CRT):又称孙子定理,是数论中的一个定理。即如果一个人知道了一个数n被多个整数相除得到的...
  • 2、掌握经典机器学习理论和算法 如果有时间可以为自己建立一个机器学习的知识图谱,并争取掌握每一个经典的机器学习理论和算法,我简单地总结如下: 1) 回归算法: 常见的回归算法包括最小二乘法(Ordinary Least ...
  • 洛谷 P1082 [NOIP2012 提高组] 同余方程 刷一刷数论的题,这才知道有扩展欧几里得算法这个东西(扩欧)。虽然还不知道欧几里得算法是什么,就一步步来看。 欧几里得算法,在《整除与剩余》板块找到了。 求两个数a,b...
  • 第三章:操作系统--调度算法 Tips: 各种调度算法的学习思路 算法思想 算法规则 这种调度算法是用于作业调度还是进程调度? 抢占式?非抢占式? 优缺点 是否会导致饥饿 1、先来先服务(FCFS) 1.1、概述 算法...
  • 算法工程师的自我修养

    千次阅读 2021-03-23 09:10:13
    看过星爷电影《喜剧之王》的人都知道,在电影中出现的一本书叫《演员的自我修养》,...那么算法工程师(这里本来想写技术工程师的,但是太广了,由于自己是从事算法行业的,所以就写算法了)的自我修养是什么呢? 自我
  • 深度学习模型压缩算法综述(二):模型剪枝算法本文禁止转载联系作者:模型剪枝算法 :L1(L2)NormFilterPruner:主要思想:修剪策略:微调策略:残差网络的处理:缺点:FPGMNormFilterPruner:主要思想:基本原理:...
  • GA算法

    千次阅读 2021-03-13 19:30:59
    遗传算法(genetic algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程计算模型,是一种通过模拟自然进化过程搜索最优解的方法。下面我将分享自己在做GA模型的心得与困惑。 先来整理一下GA的...
  • 动态分区分配是根据进程的实际需要,动态地址为之分配内存空间,在分配时按照一定的分配算法,从空闲分区表或空闲分区链中选出一分区分配给该作业 1.首次适应算法(FF):将所有空闲分区按照地址递增的次序链接,在...
  • 死锁的处理策略之避免死锁 – 银行家算法 + 安全性算法 假设:系统中有 n 个进程,m 种资源。 银行家算法: ①检查此次申请是否超过了之前声明的最大需求数。 ②检查此时系统剩余的可用资源是否还能满足这次请求...
  • 数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理,使其成为不可读的一段代码为“密文”,使其只能在输入相应的密钥之后才能显示出原容,本篇会介绍各种加密算法。 加密介绍 第一类(SHA算法)...
  • 银行家算法

    千次阅读 2020-12-28 23:04:18
    常见死锁相关算法 银行家算法:避免死锁 资源有序分配法:预防死锁 资源分配图化简法:检测死锁 撤销进程法:解决死锁 银行家算法 算法思想 银行家算法:银行家算法是从当前状态出发,按照系统各类资源剩余量逐个...
  • 目录贪心算法贪心算法优化问题贪心算法概述贪心算法的基本要素贪心选择性质最优子结构贪心法的步骤贪心法的主要特点贪心法的正确性证明贪心算法问题举例活动安排问题问题描述算法描述代码算法正确性的证明复杂度01...
  • 计算思维四种思维之四——模式识别 模式识别,就是识别出哪些问题有共性,可以用一个方法(比如排序)来解,这样我们就可以把这些问题交给计算机算法,让它重复做,做成千上万变。 对简单的模式给予合适的输入和...
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star 前言 数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,...
  • 本文是有关魔方还原算法的第三篇,上帝算法——krof 算法。在篇一的时候说过,上帝算法那就是上帝还原魔方使用的算法嘛,上帝无所不知所以在还原的过程中每一步总是能够朝着距离还原状态更近的方向前进。因此使用...
  • 背包算法简介

    千次阅读 2021-06-07 21:56:20
    背包算法是最常见的一种DP算法。它的核心要素有三个:背包容量,物品重量,物品价值。 在不同的题目中这三要素可能表现为多种形式,比如背包容量是时间(P1048 采药),体力(P1510 精卫填海),数值(P1734 最大约...
  • 文章目录一、理论基础1、基本麻雀搜索算法2、混合正弦余弦算法和Lévy飞行的麻雀算法(ISSA)(1)融合正弦余弦算法(SCA)思想(2)Lévy飞行策略二、ISSA算法流程图三、算法性能测试四、参考文献五、Matlab仿真程序 ...
  • demons算法是一种全局坐标变换模型的配准算法,该算法使用参考图像的梯度以及参考图像与浮动图像的灰度差值来计算每一个点的坐标偏移量,从而得到参考图像与浮动图像的整幅图的坐标偏移量,并使用...
  • 本文讲述社区发现之GN算法,并给出在karate club实验数据集下的实验示例代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 384,595
精华内容 153,838
关键字:

同余算法