蓝桥杯刷题5--GCD和LCM

目录

1. GCD

1.1 性质

1.2 代码实现

2. LCM

2.1 代码实现

3. 习题

3.1 等差数列

3.2 Hankson的趣味题

3.3 最大比例

3.4 GCD


1. GCD

整数a和b的最大公约数是能同时整除a和b的最大整数,记为gcd(a, b)

1.1 性质

GCD有关的题目一般会考核GCD的性质。
  (1)gcd(a, b) = gcd(a, a+b) = gcd(a, k·a+b)
  (2)gcd(ka, kb) = k·gcd(a, b)
  (3)多个整数的最大公约数:gcd(a, b, c) = gcd(gcd(a, b), c)
  (4)若gcd(a, b) = d,则gcd(a/d, b/d) = 1,即a/d与b/d互素
  (5)gcd(a+cb, b) = gcd(a, b)

1.2 代码实现

import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        System.out.println(gcd(45, 9));                // 9
        System.out.println(gcd(0, 42));                // 42
        System.out.println(gcd(42, 0));                // 42
        System.out.println(gcd(0, 0));                 // 0
        System.out.println(gcd(20, 15));               // 5
        System.out.println(gcd(-20, 15));              // -5
        System.out.println(gcd(20, -15));              // 5
        System.out.println(gcd(-20, -15));             // -5
        System.out.println(gcd(new BigInteger("98938441343232"), new BigInteger("33422"))); // 2
    }
    public static long gcd(long a, long b) {
        if (b == 0)   return a;        
        return gcd(b, a % b);
    }
    public static BigInteger gcd(BigInteger a, BigInteger b) {
        return a.gcd(b);
    }
}

2. LCM

最小公倍数LCM(the Least Common Multiple)。a和b的最小公倍数lcm(a, b),从算术基本定理推理得到。

2.1 代码实现

    public static int gcd(int a, int b) {
        if (b == 0)        return a;        
        return gcd(b, a % b);
    }
    public static long lcm(int a, int b) {
        return (long) a / gcd(a, b) * b;
    }

3. 习题

3.1 等差数列

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        int arr[] = new int[num];
        for(int i = 0;i<num;i++){
          arr[i] = scan.nextInt();
        }
        Arrays.sort(arr);
        int min = 0;
        for(int i = 1;i<num;i++){
          min = gcd(min,arr[i] - arr[i-1]);
        }
        if(min == 0) System.out.println(num);
        else System.out.println((arr[num-1] - arr[0])/min+1);
        scan.close();
    }

    public static int gcd(int a ,int b){
      if(b==0) return a;
      return gcd(b,a%b);
    }
}

这是gcd问题。把n个数据排序,计算它们的间隔,对所有间隔做GCD,结果为公差。最少数量等于:(最大值-最小值)/公差+1

3.2 Hankson的趣味题

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 0;i<n;i++){
          int a0 = scan.nextInt();
          int a1 = scan.nextInt();
          int b0 = scan.nextInt();
          int b1 = scan.nextInt();
          int count = 0;
          for(int x = 1;x<=Math.sqrt(b1);x++){
            if(b1%x == 0){
              if(gcd(x,a0) == a1 && lcm(x,b0) == b1){
                count++;
              } 
              int y = b1 / x;
              if (x == y){
                continue; 
              }                    
              if (gcd(y, a0) == a1 && lcm(y, b0) == b1){
                count++; 
              }
            }
          }
          System.out.println(count);
        }
        scan.close();
    }

    public static int gcd(int a,int b){
      if(b==0) return a;
      return gcd(b,a%b);
    }

    public static int lcm(int a,int b){
      return a/gcd(a,b)*b;
    }
}

3.3 最大比例

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        long arr[] = new long[num];
        for(int i = 0;i<num;i++){
          arr[i] = scan.nextLong();
        }
        Arrays.sort(arr);
        long q = Long.MAX_VALUE;
        long t0 = 0;
        long t1 = 0;
        for(int i = 0;i<num-1;i++){
          if(arr[i+1]!=arr[i] && arr[i+1]/arr[i] < q){
            q = arr[i+1]/arr[i];
            t0 = arr[i];
            t1 = arr[i+1];
          }
        }
        long k = gcd(t0,t1);
        System.out.println(t1/k + "/" + t0/k);
        scan.close();
    }
    public static long gcd(long a,long b){
      if(b==0) return a;
      return gcd(b,a%b);
    }
}

3.4 GCD

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long a = scan.nextLong();
        long b = scan.nextLong();
        long c = Math.abs(a-b);
        System.out.println(c - a%c);
        scan.close();
    }
}

根据更相减损术可以知道一个等式:gcd(a,b)=gcd(a,b-a) 当然这里的前提是a<=b; 所以gcd(a+k,b+k)=gcd(a+k,b-a) 这里的a和b都是已知的 我们可以设c=b-a 即c是已知的 所以想要使得a+k与c的最大公因子尽可能地大 因为最大最大能到达c 显然这个式子的最大gcd一定为 c ,我们只需要计算出a 最少需要增加多少可以成为 c 的倍数,这个增量即是答案k 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/446670.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

国家医保局开通异地就医备案办理功能,哪些人群适用?

2022年6月30日&#xff0c;国家医保局会同财政部印发《关于进一步做好跨省异地就医基本医疗保险直接结算工作的通知》&#xff08;民保发〔2022〕30号&#xff09;。 22号文&#xff08;以下简称《通知》&#xff09;。 《通知》明确&#xff0c;长期跨省异地居住或临时跨省外出…

PostgreSQL数据优化——死元组清理

最近遇到一个奇怪的问题&#xff0c;一个百万级的PostgreSQL表&#xff0c;只有3个索引。但是每次执行insert或update语句就要几百ms以上。经过查询发现是一个狠简单的问题&#xff0c;数据库表死元组太多了&#xff0c;需要手动清理。 在 PG 中&#xff0c;update/delete 语句…

Axure原型设计项目效果 全国职业院校技能大赛物联网应用开发赛项项目原型设计题目

目录 前言 一、2022年任务书3效果图 二、2022年任务书5效果图 三、2022年国赛正式赛卷 四、2023年国赛第一套样题 五、2023年国赛第二套样题 六、2023年国赛第三套样题 七、2023年国赛第四套样题 八、2023年国赛第七套样题 九、2023年国赛正式赛题&#xff08;第八套…

点赞功能真的有必要上 Redis 吗?(Mongo、MySQL、Redis、MQ 实测性能对比)

目录 一、你会怎么设计一个点赞功能&#xff1f; 1.1、点赞实现思路 1.2、点赞功能设计 1.2.1、MySQL 单表 1.2.2、单表 MySQL 关联表 1.2.3、MySQL 关联表 mq 1.2.4、redis mq 1.2.5、mongodb 关联文档 二、性能测试 2.1、前置说明 2.2、10 万数据准备 一、你会…

PyTorch完整的神经网络模型训练(使用GPU训练)

1.什么是CUDA&#xff1a; CUDA&#xff08;Compute Unified Device Architecture&#xff09;是由NVIDIA开发的一种并行计算平台和编程模型。它允许开发者在NVIDIA GPU上进行通用目的的并行计算&#xff0c;包括深度学习、科学计算、图形处理和加密等任务。 CUDA通过提供一组…

vulhub中Weblogic WLS Core Components 反序列化命令执行漏洞复现(CVE-2018-2628)

Oracle 2018年4月补丁中&#xff0c;修复了Weblogic Server WLS Core Components中出现的一个反序列化漏洞&#xff08;CVE-2018-2628&#xff09;&#xff0c;该漏洞通过t3协议触发&#xff0c;可导致未授权的用户在远程服务器执行任意命令。 访问http://your-ip:7001/consol…

人工智能:探索智慧的未来

目录 前言1 人工智能的简介1.1 人工智能的定义1.2 任务范围1.3 模拟人类认知 2 人工智能发展2.1 起步阶段2.2 发展阶段2.3 繁荣阶段 3 弱人工智能和强人工智能3.1 弱人工智能&#xff08;ANI&#xff09;3.2 强人工智能&#xff08;AGI&#xff09; 4 人工智能主要技术4.1 机器…

【C++11】包装器和bind

文章目录 一. 为什么要有包装器&#xff1f;二. 什么是包装器&#xff1f;三. 包装器的使用四. bind 函数模板1. 为什么要有 bind &#xff1f;2. 什么是 bind ?3. bind 的使用场景 一. 为什么要有包装器&#xff1f; function 包装器&#xff0c;也叫作适配器。C 中的 funct…

Elastic Stack--06--JavaAPI----索引(创建-查询- 删除)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 环境准备添加依赖&#xff1a;HelloElasticsearch JavaAPI-索引1.创建2.查询3.删除 环境准备 添加依赖&#xff1a; <dependencies><dependency><g…

第G3周:CGAN入门|生成手势图像

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制 一、前置知识 CGAN&#xff08;条件生成对抗网络&#xff09;的原理是在原始GAN的基础上&#xff0c;为生成器和判别器提供 额外的条件信息…

vue3 ref获取子组件显示 __v_skip : true 获取不到组件的方法 怎么回事怎么解决

看代码 问题出现了 当我想要获取这个组件上的方法时 为什么获取不到这个组件上的方法呢 原來&#xff1a; __v_skip: true 是 Vue 3 中的一个特殊属性&#xff0c;用于跳过某些组件的渲染。当一个组件被标记为 __v_skip: true 时&#xff0c;Vue 将不会对该组件进行渲染&am…

ABAP接口-RFC连接(ABAP TO ABAP)

目录 ABAP接口-RFC连接&#xff08;ABAP TO ABAP&#xff09;创建ABAP连接RFC函数的调用 ABAP接口-RFC连接&#xff08;ABAP TO ABAP&#xff09; 创建ABAP连接 事务代码&#xff1a;SM59 点击创建&#xff0c;填写目标名称&#xff0c;选择连接类型&#xff1a; 填写主机名…

打卡--MySQL8.0 一(单机部署)

一路走来&#xff0c;所有遇到的人&#xff0c;帮助过我的、伤害过我的都是朋友&#xff0c;没有一个是敌人。如有侵权&#xff0c;请留言&#xff0c;我及时删除&#xff01; MySQL 8.0 简介 MySQL 8.0与5.7的区别主要体现在&#xff1a;1、性能提升&#xff1b;2、新的默认…

02-app端文章查看,静态化freemarker,分布式文件系统minIO

app端文章查看&#xff0c;静态化freemarker,分布式文件系统minIO 1)文章列表加载 1.1)需求分析 文章布局展示 1.2)表结构分析 ap_article 文章基本信息表 ap_article_config 文章配置表 ap_article_content 文章内容表 三张表关系分析 1.3)导入文章数据库 1.3.1)导入数据…

【vue.js】文档解读【day 2】 | 响应式基础

如果阅读有疑问的话&#xff0c;欢迎评论或私信&#xff01;&#xff01; 本人会很热心的阐述自己的想法&#xff01;谢谢&#xff01;&#xff01;&#xff01; 文章目录 响应式基础声明响应式状态(属性)响应式代理 vs 原始值声明方法深层响应性DOM 更新时机有状态方法 响应式…

电脑数据安全新防线:文件备份的终极指南

一、数据守护者的使命&#xff1a;文件备份的重要性 在数字化日益普及的今天&#xff0c;电脑已成为我们日常生活和工作的必备工具&#xff0c;文件作为我们储存、交流和处理信息的主要载体&#xff0c;其重要性不言而喻。然而&#xff0c;无论是由于硬件故障、软件崩溃&#…

Autosar教程-Mcal教程-GPT配置教程

3.3GPT配置、生成 3.3.1 GPT配置所需要的元素 GPT实际上就是硬件定时器,需要配置的元素有: 1)定时器时钟:定时器要工作需要使能它的时钟源 2)定时器分步:时钟源进到定时器后可以通过分频后再给到定时器 定时器模块选择:MCU有多个定时器模块,需要决定使用哪个定时器模块作…

【动态规划】代码随想录算法训练营第三十九天 |62.不同路径,63.不同路径II(待补充)

62.不同路径 1、题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 2、文章讲解&#xff1a;代码随想录 3、题目&#xff1a; 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右…

JavaScript高级Ⅱ(全面版)

接上文 JavaScript高级Ⅰ JavaScript高级Ⅰ(自认为很全面版)-CSDN博客 目录 第2章 DOM编程 2.1 DOM编程概述 2.1.4 案例演示(商品全选) 2.1.5 dom操作内容 代码演示&#xff1a; 运行效果&#xff1a; 2.1.6 dom操作属性 代码演示&#xff1a; 运行效果&#xff1a; 2…

H264/265编码参数2: Profile Level Tier

profile和level profile和level是视频编码中两个很重要的概率&#xff0c;中文一般叫做档次和级别。 在MPEG2标准里边&#xff0c;按不同的压缩比分成五个档次&#xff0c;按视频清晰度分为四个级别&#xff0c;如下图所示&#xff1a; 档次和级别共有 20 种组合&#xff0c;…