【算法标签】 数学推导/数论
【语法标签】 :数组、for循环
- 小糖果重 X 克,大糖果重 Y 克(X<Y),数量无限。
- 有 N 个孩子,第 i 个孩子必须得到 Ai 颗糖果(总数)。
- 每个孩子的糖果总重量必须相等。
- 问:是否存在这样的分发方式?如果存在,求大糖果总数的最大值;否则输出
-1。
设每个孩子的总重量为 W,对于第 i 个孩子,设他拿到 bi 颗大糖果,ai 颗小糖果,则:
{ai+bi=Aiai⋅X+bi⋅Y=W
消去 ai:
(Ai−bi)X+biY=WAiX+bi(Y−X)=W
令 D=Y−X(显然 D>0),则:
bi=DW−AiX
因为 bi 必须是整数,且 0≤bi≤Ai,所以:
- 所有 W−AiX 必须能被 D 整除;
- 对每个 i,0≤DW−AiX≤Ai。
设 W=A1X+k⋅D,则对所有 i,W−AiX 必须是 D 的倍数,即:
A1X+kD−AiX≡0(modD)(A1−Ai)X≡0(modD)
令 g=gcd(X,D),X′=X/g,D′=D/g,则条件变为:
(A1−Ai)X′≡0(modD′)
因为 gcd(X′,D′)=1,所以等价于:
A1−Ai≡0(modD′)
这是存在解的必要条件,若不满足则直接输出 -1。
由 0≤bi≤Ai:
0≤DW−AiX≤AiAiX≤W≤AiX+AiD=AiY
所以 W 必须同时满足:
max(AiX)≤W≤min(AiY)
如果 max(AiX)>min(AiY),则无解。
我们需要在这个区间内,找到一个 W,使得 W≡A1X(modD),并且使 ∑bi 最大。
因为 bi=DW−AiX,所以 ∑bi=D1(NW−X∑Ai),要最大化 ∑bi,等价于最大化 W。