首页 > [NOIP2017]小凯的疑惑
开通博客写题解
头像 savage
发表于 2019-09-02 23:17:38
题目描述 小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 savage
发表于 2019-09-06 17:57:16
算法知识点: 数论 时间复杂度： 解题思路： 结论题： 如果 均是正整数且互质，那么由 不能凑出的最大数是 。 C++ 代码： #include <cstdio> #include <cstring> #i 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 RandolphJ
发表于 2019-11-30 19:34:15
P3951 小凯的疑惑 数论极菜的小萌新我刚看这题时看不懂exgcd做法的题解，后来在网上找到了一篇博客，感觉代码和推导都更加清新易懂，于是在它的基础上写了题解qwq 分析 两数互质，且有无限个，想到不定方程ax+by=gcd(a,b)=1，并且是一定有解的 对于合法的数k,可以表示为 k=a×x1 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 我是一个小雪糕啊小雪糕
发表于 2019-08-22 17:36:46
http://pre.ac.nowcoder.com/acm/problem/blogs/52041
去ta的博客 赞 (1) 回复(0) 收起
头像 paulinE
发表于 2019-08-22 17:46:17
ascgas u
去ta的博客 赞 (1) 回复(0) 收起
头像 DeepLoveNew
发表于 2021-08-26 22:30:05
时间限制，暴力法失效 设物品价格为m，已知a和b互质 若m只能被a表示，则m最小为（a-1）*b 若m只能被b表示，则m最小为（b-1）*a 若m可同时被a和b表示，则m最小为a*b 因此，要使得m既不能被a表示，也不能被b表示，则m最大为a*b-a-b #incl 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 GUYIJUN
发表于 2022-10-23 16:59:03
这是一道数论题，正如各位大佬所讲。 看到这道题，我首先想的就是打表。但是数据太大，显然打表占用空间太多。 但是，我们可以打一个小一点的表，比如20×2020\times2020×20（点表示gcd⁡(a,b)≠1\gcd(a,b)\neq1gcd(a,b)​=1）： 然后整齐的等差数列成功地引起 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”