蓝桥杯 买不到的数目

问题描述

小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候,他就用这两种包装来组合。当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。
你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。

输入格式

两个正整数,表示每种包装中糖的颗数(都不多于1000)

输出格式

一个正整数,表示最大不能买到的糖数

样例输入1
4 7
样例输出1
17
样例输入2
3 5
样例输出2
7

方法一:运用数论知识
对于互质的两个数p,q,px py 不能表示的最大数为pq-p-q.

证明:(借鉴自大神 看不懂的朋友可以搜百度理解)

先证:pq-p-q不能被px py表示.

假设pq-p-q可以被px py表示

那么 px py=pq-p-q -> q|x 1 p|y 1

很明显x 1>=q

p(x 1)>=pq 矛盾

所以pq-p-q不能被px py表示.

再证:大于pq-p-q的数一定可以用px qy表示(x>=0 y>=0)

(p-1)(q-1)=pq-p-q 1

对于n>pq-q-p即n>=(q-1)(p-1)

gcd(p,q)=1

对于z<min{p,q}存在a,b使得ap bq=z

不妨设a>0>b,显然a>0

那么如果a>q,取a1=a-q,b1=b p

那么有a1p b1q=z.

如果a1>q,可以继续以得到

Ap Bq=z,且0<|A|<q,0<|B|<p

pq-p-q=(p-1)q-q=(q-1)p-p

对于n>pq-q-p

n=pq-q-p k*min{p,q} r

r<z<min{p,q}

那么取A,B

Ap Bq=r,且0<|A|<q,0<|B|<p

不妨设A>0

n=pq-q-p k*min{p,q} r

=(q-1)p-p k*min{p,q} Ap Bq

=(A-1)p (B q-1)p k*min{p,q}

其中(A-1),(B q-1)>=0

那么无论min{p,q}是p还是q,都有

对于n>pq-q-p,都可以表示成px qy

#include <iostream>
using namespace std;
int main(int argc, char *argv[]) {
int a,b;
cin >> a >> b;
cout << a*b-a-b;
return 0;
}

方法二就比较接地气了hhh:

#include <iostream>
using namespace std;
#define N 50000
int c[N];
void check(int a,int b){
for(int i=0;i<=N/a;i  ){ //去掉多余循环,下同;
for(int j=0;j<=(N-i*a)/b;j  ){
if(i*a   j*b < N) c[i*a   j*b] = 1;
}
}
}
int count(int min){
int time = 0;
for(int i=0;i<=N;i  ){
if(c[i] == 1) time  ;
else time = 0;
//连续a个或者b个数(min取自ab)都可被表示出,则后面的数都能表示了,例如3和5两个数, 8,9,10连续3个数都可被表示,则后面的数就都能表示了,最大值就是10-min = 7;
if(time == min) return i - time;
}
return -1;

}
int main(int argc, char *argv[]) {
int a,b;
cin >> a >> b;
int min;
a < b ? min=a : min=b;//选择小值传入
check(a,b);
cout << count(min);
return 0;
}

来源:https://www.icode9.com/content-4-885501.html

(0)

相关推荐

  • ​LeetCode刷题实战23:合并K个升序链表

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 实时监控(官方文档)

    Sentinel 提供对所有资源的实时监控.如果需要实时监控,客户端需引入以下依赖(以 Maven 为例): <dependency> <groupId>com.alibaba ...

  • 算法创作|蓝桥杯真题分糖果问题解决方法

    问题描述有n个小朋友围坐成一圈.老师给每个小朋友随机发偶数个糖果,然后进行下面的游戏:每个小朋友都把自己的糖果分一半给左手边的孩子.一轮分糖后,拥有奇数颗糖的孩子由老师补给1个糖果,从而变成偶数.反复 ...

  • Python | 蓝桥杯-幸运数字的解决方法

    问题描述 到x星球旅行的游客都被发给一个整数,作为游客编号.x星的国王有个怪癖,他只喜欢数字3,5和7. 国王规定,游客的编号如果只含有因子:3,5,7,就可以获得一份奖品. 前10个幸运数字是:3 ...

  • 算法创作|蓝桥杯关于成绩统计问题解决方法

    标题问题描述示例:小蓝给学生们组织了一场考试,卷面总分为 100 分,每个学生的得分都是一个 0 到 100 的整数.如果得分至少是 60 分,则称为及格.如果得分至少为 85 分,则称为优秀.请计算 ...

  • 算法创作|蓝桥杯——排列序数问题解决方法

    问题描述示例:如果用a b c d这4个字母组成一个串,有4!=24种,如果把它们排个序,每个串都对应一个序号:abcd  0abdc  1acbd  2acdb  3adbc  4adcb  5ba ...

  • 算法创作|2020蓝桥杯真题-跑步锻炼

    问题描述小蓝每天都锻炼身体.正常情况下,小蓝每天跑 1 千米.如果某天是周一或者月初(1 日),为了激励自己,小蓝要跑 2 千米.如果同时是周一或月初,小蓝也是跑 2 千米.小蓝跑步已经坚持了很长时间 ...

  • Python | 2020蓝桥杯真题-寻找2020

    问题描述小蓝有一个数字矩阵,里面只包含数字 0 和 2.小蓝很喜欢 2020,他想找到这个数字矩阵中有多少个 2020 .小蓝只关注三种构成 2020 的方式:· 同一行里面连续四个字符从左到右构成 ...

  • 2019蓝桥杯-矩形切割

    问题描述当他面对一块矩形材料时,他总是从中间切割一刀,切出一块最大的正方形,剩下一块矩形,然后再切割剩下的矩形材料,直到全部切为正方形为止.例如,对于一块两边分别为 5 和 3 的材料(记为 5×3) ...

  • 算法创作|蓝桥杯-体力消耗问题解决方法

    问题描述用文字描述要解决的问题是什么.示例:小明要做一个跑步训练.初始时,小明充满体力,体力值计为 10000.如果小明跑步,每分钟损耗600 的体力.如果小明休息,每分钟增加300的体力.体力的损耗 ...

  • Python|2020年蓝桥杯:蛇形填数

    问题描述如下图所示,小明用从 1 开始的正整数"蛇形"填充无限大的矩阵.1 2 6 7 15 -3 5 8 14 -4 9 13 -10 12 -11 --(1)容易看出矩阵第二行 ...