Skip to content

Latest commit

 

History

History
128 lines (90 loc) · 3.24 KB

File metadata and controls

128 lines (90 loc) · 3.24 KB
comments difficulty edit_url tags
true
中等
数学
动态规划
数论

English Version

题目描述

给定两个 不同的质数 primeOne 和 primeTwo

Alice 和 Bob 正在逛市场。该市场有 无数种 商品,对于 任何 正整数 x,都存在一个价格为 x 的物品。Alice 想从市场里买一些东西送给 Bob。她有 无数个 面值为 primeOneprimeTwo 的硬币。她想知道她 无法 用她拥有的硬币购买的 最贵 商品的价格。

返回 Alice 无法买给 Bob 的 最贵 商品的价格。

 

示例 1:

输入:primeOne = 2, primeTwo = 5
输出:3
解释:无法购买的商品的价格有 [1,3]。所有价格大于 3 的商品都可以通过组合使用面额为 2 和 5 的硬币购买。

示例 2:

输入:primeOne = 5, primeTwo = 7
输出:23
解释:无法购买的商品的价格有 [1,2,3,4,6,8,9,11,13,16,18,23]。所有价格大于 23 的商品都可以购买。

 

提示:

  • 1 < primeOne, primeTwo < 104
  • primeOne, primeTwo 都是质数。
  • primeOne * primeTwo < 105

解法

方法一:Chicken McNugget 定理

根据 Chicken McNugget 定理,两个互质的正整数 $a$$b$,最大不能表示的数为 $ab - a - b$

时间复杂度 $O(1)$,空间复杂度 $O(1)$

Python3

class Solution:
    def mostExpensiveItem(self, primeOne: int, primeTwo: int) -> int:
        return primeOne * primeTwo - primeOne - primeTwo

Java

class Solution {
    public int mostExpensiveItem(int primeOne, int primeTwo) {
        return primeOne * primeTwo - primeOne - primeTwo;
    }
}

C++

class Solution {
public:
    int mostExpensiveItem(int primeOne, int primeTwo) {
        return primeOne * primeTwo - primeOne - primeTwo;
    }
};

Go

func mostExpensiveItem(primeOne int, primeTwo int) int {
	return primeOne*primeTwo - primeOne - primeTwo
}

TypeScript

function mostExpensiveItem(primeOne: number, primeTwo: number): number {
    return primeOne * primeTwo - primeOne - primeTwo;
}

Rust

impl Solution {
    pub fn most_expensive_item(prime_one: i32, prime_two: i32) -> i32 {
        prime_one * prime_two - prime_one - prime_two
    }
}