问题分析

这是一个线性组合最优化问题。需要购买两种不同规格的花束（第一家店：$A$ 支/$B$ 元；第二家店：$C$ 支/$D$ 元），使得总花数至少为 $N$，同时总花费最小。

核心思路

1. 成本效率比较

• 首先比较两家店的单位成本效率：$\frac{B}{A}$ vs $\frac{D}{C}$
• 通过交换确保第一家店的花束更具成本效益（单位花的价格更低）

2. 关键数学洞察

• 问题可转化为求解线性丢番图方程的最优整数解
• 利用数论性质：由于花束数量必须是整数，最优解具有周期性
• 只需要在有限的范围内枚举其中一家的购买数量即可找到全局最优解

3. 枚举优化

• 直接枚举所有可能的购买组合不可行（$N$ 可达 $10^{15}$）
• 通过计算 $A$ 和 $C$ 的最大公约数，将枚举范围从 $O(N)$ 降至 $O(\max(A,C))$
• 只需枚举模某个周期内的可能情况即可覆盖所有最优解候选

算法特点

1. 时间复杂度：$O(\max(A,C))$，通过数论优化避免超大规模枚举
2. 空间复杂度：$O(1)$，仅需常数额外空间
3. 正确性保证：基于线性丢番图方程和模运算的理论基础

解决效果

该算法能够高效处理极大的 $N$ 值（$10^{15}$），通过巧妙的数学变换将问题规模压缩到可计算范围内，确保在合理时间内找到购买至少 $N$ 支花的最小成本方案。