首页 > 其他分享 >小凯的疑惑

小凯的疑惑

时间:2023-07-28 20:23:22浏览次数:40  
标签:小凯 疑惑 ab times 金币 le ax

题目

小凯的疑惑

题面

[NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目

题目背景

NOIP2017 提高组 D1T1

题目描述

小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。

现在小凯想知道在无法准确支付的物品中,最贵的价值是多少金币?

注意:输入数据保证存在 小凯无法准确支付的商品。

输入格式

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

输出格式

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

样例 #1

样例输入 #1


 3 7

样例输出 #1


 11

提示

【输入输出样例 1 说明】

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

\(12 = 3 \times 4 + 7 \times 0\);

\(13 = 3 \times 2 + 7 \times 1\);

\(14 = 3 \times 0 + 7 \times 2\);

$15 = 3 \times 5 + 7 \times 0 $。

【数据范围与约定】

对于 \(30\%\) 的数据: $1 \le a,b \le 50 $。

对于 \(60\%\) 的数据: $1 \le a,b \le 10^4 $。

对于$ 100%$ 的数据:$1 \le a,b \le 10^9 $。

题意

给你两个互质的数,询问不可以用这连个数累加表示的最大的数字

题解

这道题木只需要用瞪眼法就可以看出是一道数论的题目,再根据中学的盲猜发就可以看出通项公式:\(ans=a \times b-a-b\)
接着再加以证明就好了

证明:

存在性:

     根据乘法的分配律得出:\(a(b-1)=ab-a\)
     因为\(a,b\)互质,\(b\),\(b-1\)互质,所以\(b\)不能表示为\(ab-a\)
     所以就不能表示出\(ab-a-b\)
     同理,\(a\)可以表示出\(a(b-1)\),无法表示出ab-a-b

最大性:

     因为\(a,b\)是整数,且\(gcd(a,b)=d\)
     那么对于任意的整数\(x\),\(y\),\(ax+by\)都一定是d的倍数
     并且一定存在整数\(x,y\),使\(ax+by=d\)成立。
     不妨设\(b>x\),等价于\(b≥x+1\)
     即证明:\(by=n-ax>ab-a-b-ax=ab-a(x+1)-b\)
     因为\(b≥1+x\),所以\(ab-a(x-1)-b≥-b\)
     所以\(n-ax>-b\),所以\(by>-b\),所以\(y>=0\)。而恰好,\(y>=0\)。

得证:

     \(ans=a \times b-a-b\)

AC code


#include <bits/stdc++.h>
using namespace std;
long long a, b;
int main()
{
    cin >> a >> b;
    cout << a * b - a - b << endl;
    return 0;
}

标签:小凯,疑惑,ab,times,金币,le,ax
From: https://www.cnblogs.com/liudagou/p/17588745.html

相关文章

  • OceanBase执行信息的疑惑
    需要明确的信息:ps_stmt_id:当该值为0时,代表执行计划是从远端传输过来的从上述查询中,可以得到的信息是,plan_id=1091310631对应的ps_stmt_id为0,说明该执行计划是从远端传输过来的,该执行计划type=1,说明只能从type=2且ps_stmt_id值非0的节点传输过来,那么也就是从plan_id=13248941传......
  • P3951 小凯的疑惑 / 买不到的数目【这题简单】
    基础数论题花了一会儿,不难想出来题意:求互质的两个数\(a,b\)的线性组合所不能表示的最大数字这题简单,设\(a<b\)如果一个数\(k\)可以被表示,哪么就可以写成:\(k=x*a+y*b\)例如5,9,将非负整数划分为许多个区间\([n*b,(n+1)*b)\),分别为:\([0,9),[9,18),[18,27)\)......
  • 关于你的类该是什么包装类还是基础类型的疑惑?例如Long和long
    解释一下在Java中,long是基本数据类型,而Long是对应的包装类。DTO实体类中需要使用长整型的属性时,应该使用Long而不是long。这是因为DTO实体类通常用于数据传输,而数据传输过程中需要使用对象,而非基本数据类型。另外,使用Long能够提供更好的灵活性和安全性,因为它可以为null......
  • 关于final关键字的几点疑惑和答案
    问题:被final修饰的变量在内存中的位置?问题:为什么被final修饰的变量必须进行立即初始化或者构造方法初始化?问题:为什么局部变量必须要进行显示初始化?问题:为什么方法内部类访问方法的局部变量时必须加final修饰符?final从字面上理解含义为“最后的,最终的”。在Java中也同样表示......
  • P4942 小凯的数字
    P4942小凯的数字题目和数据范围提示有\(O(1)\)作法。直接拆数字,会TLE$res\mod9=l(l+1)(l+2)...(r-1)r\mod9$找规律不难发现\(\texttt{所有数位的数字之和}\mod9\)即为答案。但直接求所有数位之和明显不行,(数位dp好像可以,也许吧没试过)观察到不需要求出所有......
  • 对应用数据开发还有疑惑?看这篇就够了!数据存储、管理,通通掌握!
     原文:https://mp.weixin.qq.com/s/0YzFUfx-1ZdfOQhaeekwhg,点击链接查看更多技术内容。数据管理可以做什么?应用数据的持久化怎么实现?如何实现数据库加密?在开发应用进行应用数据的处理时,您是否也会有这些疑问呢?现在,我们推出了更为清晰完善的数据管理文档,帮助开发者明确各种......
  • 小T的疑惑
    7-3小T的疑惑(20分)小T是一个非常无聊的人,没事就喜欢偷听别人聊天。某天他在食堂排队时听到大一的新同学们在聊天,于是他也凑了过去。听到如下谈话:小L:我和小Z是同学。小Z:我和小H是同学。小H:我和小R是同学。小B:我和小A是同学。小Z:我和小Z是同学。小T想知道,聊天的这些同学......
  • 《JavaScript权威指南第七版》13.3.4实现细节,关于“ES2017解释器可以把函数体分割成一
    读到“ES2017解释器可以把函数体分割成一系列独立的子函数,每个子函数都被传给位于他前面以await标记的那个期约的then方法”这一部分是比较困惑,也没有代码示例,很抽象,不易理解。自己写了个例子来复述一下这段话:functiongetPosts(){returnnewPromise(function(resolve,......
  • java链表的疑惑
    head.next=tail; tail=newListNode();为什么head.next不等于tail在cpp里面head->next=tail;tail=newListNode();这时head->next==tail.这是因为head->next存放的是tail的地址,而java中head.next=tail; tail=newListNode();head.next存放的是tail的之前......
  • 对于Object中一些方法的疑惑与理解
    getClass这是生成字节码文件对象的三种方式之一,由任意对象调用getClass(Object中定义的方法)可以返回该类的字节码文件对象,一般一般用于反射getName该方法是,Class类中定义的一个方法,用于返回字节码文件对象所表示的实体(类或者接口)的全类名2023.5.4对于向上转型和任何类型都可以......