[第四届蓝桥杯省赛C++A组]买不到的数目
C++ 蓝桥 省赛 数目 第四届
2023-09-11 14:18:49 时间
来源: 第四届蓝桥杯省赛C++A组
算法标签:数学
题目描述
小明开了一家糖果店。
他别出心裁:把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。
小朋友来买糖的时候,他就用这两种包装来组合。
当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。
你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。
大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。
输入格式
两个正整数 n,m,表示每种包装中糖的颗数。
输出格式
一个正整数,表示最大不能买到的糖数。
数据范围
2≤n,m≤1000,
保证数据一定有解。
输入样例:
4 7
输出样例:
17
思路
(裴蜀定理) O(1)
裴蜀公式:p*q-p-q
引理:给定a,ba,b,若d=gcd(a,b)>1d=gcd(a,b)>1,则一定不能凑出最大数
结论:
如果 a,ba,b 均是正整数且互质,那么由 ax+by,x≥0,y≥0ax+by,x≥0,y≥0 不能凑出的最大数是 (a−1)(b−1)−1(a−1)(b−1)−1。
C++ 代码
#include<iostream>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
cout<<a*b-a-b;
return 0;
}
20201013
#include<iostream>
using namespace std;
#define f(a,b) (a*b-a-b)
int main(){
int a,b;
cin>>a>>b;
cout<<f(a,b);
return 0;
}
相关文章
- Java实现第十一届蓝桥杯C/C++ 大学 B 组大赛软件类 省赛真题(希望能和各位大佬能一起讨论算法题:讨论群:99979568)
- Java实现第十一届蓝桥杯C/C++ 大学 B 组大赛软件类省赛
- java实现第二届蓝桥杯连通问题(C++)
- 第五届蓝桥杯C++B组国(决)赛真题
- 第四届蓝桥杯C++B组国(决)赛真题
- 你该怎么学习C++——思想层面
- 第十二届蓝桥杯省赛第二场C++B组真题(节选)
- windows下使用vim(gVim)和gcc(MinGW):C/C++/Fortran/ObjC/Ada Compiler
- 蓝桥杯官网 试题 PREV-94 历届真题 矩阵计数【第十届】【决赛】【研究生组】【C++】解法
- 蓝桥杯官网 试题 PREV-115 历届真题 轨道炮【第十届】【决赛】【研究生组】【C++】【Java】两种解法
- 蓝桥杯官网 试题 PREV-61 历届真题 装饰珠【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 蓝桥杯官网 试题 PREV-265 历届真题 砝码称重【第十二届】【省赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 【面试攻略】C++面试-边锋
- 【C++服务端技术】移动广播
- 初探C++类模版学习笔记
- 拆除vs发展c++程序开发过程中产生的.ipch和.sdf文件的方法
- VC++通过修改manifest文件来解决Vista/Win7/Win8下应用程序兼容性问题(附源码)
- 第十三届蓝桥杯省赛 C++ C 组 I 题、Python B 组 H题——技能升级(AC)
- 第十三届蓝桥杯省赛 C++ A 组 F 题、Java A 组 G题、C组 H 题、Python C 组 I 题——青蛙过河(AC)
- 第十三届蓝桥杯省赛C++组、Java组真题—— 求和 (AC)
- 第十三届蓝桥杯省赛C++A组 D 题、C++C组 F 题、Java C 组 F 题——选数异或 (AC)
- 第十三届蓝桥杯JavaA组、C++A组省赛 J 题——推导部分和 (AC)
- 第十三届蓝桥杯C++B组国赛F题——费用报销 (AC)
- 第十三届蓝桥杯C++B组国赛I题——齿轮 (AC)
- C++Primer学习笔记4-基本函数
- 第十三届蓝桥杯B组C++(试题C:刷题统计)
- ShiDianNao的c++实现