网站首页 站内搜索

搜索结果

查询Tags标签: GCD,共有 180条记录
  • P1516 青蛙的约会

    题目传送门 思路 因为两个青蛙同时跳到同一个点上才算碰面,设 $ t $ 为跳的次数, $ p $ 为两个青蛙跳的圈数之差,有如下式子: \[(x+m \times t ) - ( y+n \times t ) = p \times L \]整理得: \[(n-m) \times t + L \times p = x - y \]首先,要判断 $ \gcd ( n-m ,…

    2022/7/31 23:39:32 人评论 次浏览
  • 扩展欧几里得算法exgcd基本运用 与 exgcd求逆元

    基础用法 给定 $ n $ 对正整数 $ a_i, b_i $,对于每对数,求出一组 $ x_i, y_i $,使其满足 $ a_i \times x_i + b_i \times y_i = gcd(a_i, b_i) $。 裴蜀定理 对于任意正整数\(a, b\),那么一定存在非零整数\(x,y\)使得\(ax + by = gcd(a , b )\)假设\(ax + by = d\)…

    2022/7/24 14:23:15 人评论 次浏览
  • 2022.7.16 递归算法

    递归的概念 当在函数的定义中,其操作又直接或间接地出现对自身的调用,则称这样嵌套定义为递归。 递归通常把一个大型问题层层转化为一个与原问题相似的规模较小的问题来解决。 核心思想为\(\color{red}{用少量的程序描述出解题过程所需要的多久重复计算,大大减少了代码…

    2022/7/17 1:15:11 人评论 次浏览
  • #D220712C. 小 C 的序列

    #D220712C. 小 C 的序列 题目描述 小 C 现在得到了两个序列 \(A = {a_1, a_2, ..., a_n}\) \(B = {b_1, b_2, ..., b_m}\)。他想知道对于每个 \(B\) 中 的数 \(b_i\),有多少个 \(A\) 的子序列 \(Al,r = {a_l, a_{l+1}, .., a_r}\) 满足所有数的最大公因数为\(b_i\)。 小 …

    2022/7/12 23:31:44 人评论 次浏览
  • 密码工程-扩展欧几里得算法

    任务详情 0. 在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务 1. 参考《密码工程》p112伪代码实现ExtendedGCD(int a, int b, int *k, int *u, int *v)算法(10’) 2. 在测试代码中计算74模167的逆。(5‘) 3. 提交代码和运行结果截图代码 #include<std…

    2022/6/10 1:22:28 人评论 次浏览
  • 扩展欧几里得算法

    扩展欧几里得算法在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务 参考《密码工程》p112伪代码实现ExtendedGCD(int a, int b, int *k, int *u, int *v)算法(10’) 在测试代码中计算74模167的逆。(5‘) 提交代码和运行结果截图#include <stdio.h> …

    2022/6/10 1:22:28 人评论 次浏览
  • 密码工程-扩展欧几里得算法

    在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务 参考《密码工程》p112伪代码实现ExtendedGCD(int a, int b, int *k, int *u, int *v)算法(10’) 在测试代码中计算74模167的逆。(5‘) 提交代码和运行结果截图代码如下 //myexgcd #include<stdio.h>…

    2022/6/10 1:22:27 人评论 次浏览
  • 模拟赛t3 太阳神(ra) 题解

    太阳神 求满足如下条件的数对$(a,b)$对数:$a,b$均为正整数且$a,b \leq n$而$lcm(a,b)>n$。 答案对$10^9+7$取模 $n\leq 10^{10}$. 原题题解写的看不懂 题意即为求 $\sum _{a=1} ^{N} \sum _{b=1} ^{N} [lcm(a,b)>N]$. 转化为 $N^2-\sum _{a=1} ^{N} \sum _{b=1} ^{N…

    2022/6/6 23:21:48 人评论 次浏览
  • java 题目:输入两个正整数 m 和 n,求其最大公约数和最小公倍数。

    import java.util.Scanner;public class Pro9 {public static void main(String[] args) {// TODO Auto-generated method stubScanner in = new Scanner(System.in);int a;int b;int r;//最大公约数初值int gcd = 1;//最小公倍数int lcm = 0;System.out.println("请…

    2022/6/4 1:22:30 人评论 次浏览
  • 关于 欧几里得算法+裴蜀定理+扩展欧几里得

    一、欧几里得算法 又称辗转相除法,用于计算两个整数a,b的最大公约数 gcd(a,b)。基本算法:设 a = qb + r,其中a,b,q,r都是整数,则 gcd(a,b) = gcd(b,r),即 gcd(a,b) = gcd(b,a%b)。 证明: a = qb + r如果 r = 0,那么 a 是 b 的倍数,此时显然 b 是 a 和 b 的最大…

    2022/5/12 20:57:30 人评论 次浏览
  • CF1375I Cubic Lattice

    简要题意: 定义三维空间中的一个 lattice 是满足下列条件的三维整点的集合: \[L=\{u\cdot \overrightarrow{r_1}+v\cdot \overrightarrow{r_2}+w\cdot \overrightarrow{r_3} \}_{u,v,w\in \mathbb Z} \]其中 \(\overrightarrow{r_1},\overrightarrow{r_2},\overrightarr…

    2022/5/1 6:15:09 人评论 次浏览
  • cf1366 D. Two Divisors

    题意: 找 x 的两个大于 1 的因子 d1 和 d2,使得 \(\gcd(d1+d2,x)=1\) 思路: 性质:\(\gcd(a,b)=\gcd(a+b,b)\) 所以, \(\gcd (x,y)=1=\gcd(x+y,x)=\gcd(x+y,y)\implies \gcd(x+y,xy)=1\) 找 x 的最小素因子和它的次数 \(p^k\),答案是 \(p^k,x/p^k\)

    2022/4/19 6:13:19 人评论 次浏览
  • Codeforces Round #694 (Div. 2)

    D该题目告诉我们两个数\(x,y\)它们的\(\frac{lcm(x, y)}{gcd(x, y)}\)如果是一个完全平方数的话,我们就称它们是相邻的。 现在给我们一个长度为\(n\)的数组\(a\),每一秒数组中的每个元素\(a_i\)都被数组中与当前值相邻的所有元素(包括其自身)的乘积所取代。让\(d_i\)是每…

    2022/4/14 6:14:58 人评论 次浏览
  • [Acwing蓝桥杯数学知识] 扩展欧几里得线性同余方程

    扩展欧几里得用于求解方程 ax+by=gcd(a,b)的解 当 b=0时 ax+by=aax+by=a 故而 x=1,y=0x=1,y=0当 b≠0 时因为gcd(a,b)=gcd(b,a%b) 而bx′+(a%b)y′=gcd(b,a%b) bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)故而x=y′,y=x′−⌊a/b⌋…

    2022/3/31 6:23:55 人评论 次浏览
  • 蓝桥杯循环小数

    我们先将循环体部分转换为真分数。再通过约分和分数加法等操作完成对答案的求解。 # 求最大公约数的函数 def gcd(a,b):if a < b:a,b = b,aelif a==b:return 1while b!=0:temp = a % ba = bb = tempreturn a# 输入 p,q = map(int,input().split()) s = input() fz = i…

    2022/3/19 23:39:32 人评论 次浏览
共180记录«上一页1234...12下一页»
扫一扫关注最新编程教程