【luogu3951】【数学】小凯的疑惑_小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小 凯都有无数-程序员宅基地

技术标签: 数学  luogu  

传送门

题目描述

小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有 无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小 凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在 小凯无法准确支付的商品。

输入格式

两个正整数 a a a b b b,它们之间用一个空格隔开,表示小凯中金币的面值。

输出格式

一个正整数 N N N,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。

输入输出样例
输入 #1
3 7
输出 #1
11
说明/提示
【输入输出样例 1 说明】

小凯手中有面值为 3 3 3 7 7 7的金币无数个,在不找零的前提下无法准确支付价值为 1 , 2 , 4 , 5 , 8 , 11 1, 2,4,5,8,11 1,2,4,5,8,11的物品,其中最贵的物品价值为 11 11 11,比 11 11 11贵的物品都能买到,比如:

12 = 3 × 4 + 7 × 0 12 = 3 \times 4 + 7 \times 0 12=3×4+7×0

13 = 3 × 2 + 7 × 1 13 = 3 \times 2 + 7 \times 1 13=3×2+7×1

14 = 3 × 0 + 7 × 2 14 = 3 \times 0 + 7 \times 2 14=3×0+7×2

15 = 3 × 5 + 7 × 0 15 = 3 \times 5 + 7 \times 0 15=3×5+7×0

【数据范围与约定】

对于 30 % 30\% 30%的数据: 1 ≤ a , b ≤ 50 1 \le a,b \le 50 1a,b50

对于 60 % 60\% 60%的数据: 1 ≤ a , b ≤ 1 0 4 1 \le a,b \le 10^4 1a,b104

对于 100 % 100\% 100%的数据: 1 ≤ a , b ≤ 1 0 9 1 \le a,b \le 10^9 1a,b109


解题思路

本蒟蒻数学不好,以虾证明极度的水,请做好心里准备

先设 x x x是不能被 a a a b b b表示的最大数
x = m ⋅ a + n ⋅ b x=m·a+n·b x=ma+nb

因为 n n n为非负数时,一定是可以表示的,那么我们(反人类一下 )反转一下,把 n n n设为一个负数
为了保证 x x x最大, n n n设为-1,那么式子就不可以被 a a a表示了

x = m ⋅ a − b x=m·a-b x=mab 但是可以用 b b b表示,比如 m = b m=b m=b x = b ⋅ ( a − 1 ) x=b·(a-1) x=b(a1)
那么再把 m = b − 1 m=b-1 m=b1 x = ( b − 1 ) ⋅ a − b = a ⋅ b − a − b x=(b-1)·a-b=a·b-a-b x=(b1)ab=abab,这个式子就不可以被 b b b a a a表示了

其实吧,粗暴理解最后的结果式子会更好理解一些
x = a ⋅ b − a − b x=a·b-a-b x=abab
− a -a a时, x = a ⋅ ( b − 1 ) x=a·(b-1) x=a(b1) ,是可以被 a a a表示的,不可以被 b b b表示
− b -b b时, x = ( a − 1 ) ⋅ b x=(a-1)·b x=(a1)b ,是可以被 b b b表示的,不可以被 a a a表示
所以两个都减去就不可以被表示了


Code
#include <iostream>
#include <cstdio>
using namespace std;
long long a, b;
int main()
{
    
	scanf ("%lld%lld", &a, &b);
	printf ("%lld", a * b - a - b);
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39940018/article/details/108126166

智能推荐

记录Linux安装Oracle19c_debian 安装 oracle19c-程序员宅基地

文章浏览阅读712次。最近单位要求本渣学习服务器脚本编写完成定点市级机构下发的数据库表导入项目服务器数据库,按工作顺序就先打算在自己笔记本电脑上通过虚拟机来模拟生产环境,部署虚拟环境后安装Linux版本Oracle19c数据库。经过数天研究终完成安装,记录如下。安装准备:1、虚拟软件 Oracle VM VirtualBox2、镜像 CentOS-7-x86_64-Minimal-2009.iso3、Xshell 7.04、Xftp 7.05、Xmanager Enterprise 56、LINUX._debian 安装 oracle19c

Halcon分类器之高斯混合模型分类器_训练高斯混合模型分类器-程序员宅基地

文章浏览阅读2k次,点赞2次,收藏20次。Halcon分类器示例自我理解看了很多网上的例子,总有一种纸上得来终觉浅,绝知此事要躬行的感觉。说干就干,将Halcon自带分类器例子classify_metal_parts.hdev按照自己的理解重新写一遍,示例中的分类器是MLP(多层感知机),我将它改变为GMM(高斯混合模型)。希望可以帮助刚入门的同学学习理解,大神请绕路吧,当然也喜欢各位看官帮我找出不足之处,共同进步。谢谢!分类效果如图..._训练高斯混合模型分类器

Office转PDF工具类_"officetopdf.wordtopdf(\"d:\\\\1234.doc\", \"d:\\\-程序员宅基地

文章浏览阅读819次。使用Jacob转换office文件,Jacob.dll文件需要放到jdk\bin目录下Jacob.dll文件下载地址https://download.csdn.net/download/zss0101/10546500package com.zss.util;import java.io.File;import com.jacob.activeX.ActiveXComponent;..._"officetopdf.wordtopdf(\"d:\\\\1234.doc\", \"d:\\\\1234.pdf\");"

redis实现队列_redistemplate convertandsend方法实现队列-程序员宅基地

文章浏览阅读1k次,点赞30次,收藏30次。上面的例子我们已经了一个简易的消息队列。我们继续思考一个现实的场景,假定这些是一些游戏商品,它需要添加"延迟销售"特性,在未来某个时候才可以开始处理这些游戏商品数据。那么要实现这个延迟的特性,我们需要修改现有队列的实现。在消息数据的信息中包含延迟处理消息的执行时间,如果工作进程发现消息的执行时间还没到,那么它将会在短暂的等待之后重新把消息数据推入队列中。(延迟发送消息)_redistemplate convertandsend方法实现队列

java基础-程序员宅基地

文章浏览阅读287次,点赞5次,收藏5次。java基础篇

使用gparted对linux根目录扩容(windows+linux双系统)_双系统linux扩容-程序员宅基地

文章浏览阅读298次。linux扩容根目录与/home_双系统linux扩容

随便推点

Python使用pika调用RabbitMQ_python pika 通过主机名称来访问mq-程序员宅基地

文章浏览阅读388次。定义RabbitMQ类import jsonimport osimport sysimport pikafrom Data import Datafrom MongoDB import MongoDBfrom constants import *class RabbitMQ: def __init__(self, queue_name): """ 初始化队列对象 :param queue_name: 队列名称 "_python pika 通过主机名称来访问mq

Python利用openpyxl处理excel文件_在 python 中可以通過 openpyxl 套件來很好的操作 excel 讀寫-程序员宅基地

文章浏览阅读568次。**openpyxl简介**openpyxl是一个开源项目,openpyxl模块是一个读写Excel 2010文档的Python库,如果要处理更早格式的Excel文档,需要用到其它库(如:xlrd、xlwt等),这是openpyxl比较其他模块的不足之处。openpyxl是一款比较综合的工具,不仅能够同时读取和修改Excel文档,而且可以对Excel文件内单元格进行详细设置,包括单元格样式等内容,甚至还支持图表插入、打印设置等内容,使用openpyxl可以读写xltm, xltx, xlsm, xls_在 python 中可以通過 openpyxl 套件來很好的操作 excel 讀寫

Unity判断某个物体是否在某个规定的区域_unity判断物体在范围内-程序员宅基地

文章浏览阅读1.4w次,点赞7次,收藏56次。Unity自带的两种写法:①物体的位置是否在某个区域内Vector3 pos = someRenderer.transform.position;Bounds bounds = myBoxCollider.bounds;bool rendererIsInsideTheBox = bounds.Contains(pos);②物体的矩形与区域的矩形是否交叉Bounds rendererBo..._unity判断物体在范围内

[深度学习] 使用深度学习开发的循线小车-程序员宅基地

文章浏览阅读295次,点赞6次,收藏4次。报错:Unable to find image 'openexplorer/ai_toolchain_centos_7_xj3:v2.3.3' locally。报错: ./best_line_follower_model_xy.pth cannot be opened。可以看到生成的文件 best_line_follower_model_xy.pth。报错:Module onnx is not installed!安装onox,onnxruntime。这是由于没有文件夹的写权限。

MDB-RS232测试NAYAX的VPOS刷卡器注意事项-程序员宅基地

文章浏览阅读393次,点赞10次,收藏8次。MDB-RS232测试NAYAX的VPOS非现金MDB协议刷卡器注意事项

Pytorch和Tensorflow,谁会笑到最后?-程序员宅基地

文章浏览阅读2.5k次。作者 |土豆变成泥来源 |知秋路(ID:gh_4a538bd95663)【导读】作为谷歌tensorflow某项目的Contributor,已经迅速弃坑转向Pytorch。目前Ten..._pytorch与tensorflow