每日一练 通货膨胀-x国货币
目录
题目描述
输入描述
输出描述
题目原图
解题思路
代码实现
运行结果
难点和亮点
本次来自CSDN本站的2023年3月16日（期）题目！
题目描述
X国发行货币最高面额为n。 次高面额为n的因子。 以此类推。 X国最多发行多少种货币。
输入描述
输入整数n。(1<=n<=1000000)表示货币的最大面额
输出描述
输出货币的种类
示例：输入10，输出3
题目原图
解题思路
这道题可以用贪心的思路来解决。
首先，可以发现最大面额的货币只有一种，次大面额的货币可以是最大面额的因数，再往下，每种货币面额只能是它上一个面额的因数，所以每个面额只能由上一个面额的因数转移而来。因此，我们从最大面额开始，不断求出当前面额的因数，直到得到面额为1，这样就可以得到所有的货币种类数。
具体地，可以采用一个循环，从最大面额n开始，每次找到当前面额i的最大因数j，然后将i更新为j，继续循环，直到i等于1时结束循环，循环过程中计数器加1即可。
实现时，可以用一个while循环不断找到当前面额的最大因数，可以用i/2的方式加速查找。代码如下：
代码实现
// 请关闭中文输入法，用英文的字母和标点符号。
// 如果你想运行系统测试用例，请点击【执行代码】按钮，如果你想提交作答结果，请点击【提交】按钮，
// 注意：除答案外，请不要打印其他任何多余的字符，以免影响结果验证
// 本OJ系统是基于 OxCoder 技术开发，网址：www.oxcoder.com
// 模版代码提供基本的输入输出框架，可按个人代码习惯修改#include
#include
#include
#include int solution(int n){int result = 0;for (int i = n;i>=1;i--){if(n%i == 0) {result++;n = i;}}// TODO:return result;
}int main() {int n;std::cin>>n;int result = solution(n);std::cout< 用的是示例模板！采用的C++语言编写！
运行结果
难点和亮点
首先要想到的是，最高面额的货币肯定是必须发行的，因此最多的货币种类数目至少是1。接着，如果最高面额为n，那么次高面额一定是n的因子，次次高面额一定是次高面额的因子，以此类推，直到最低面额为1为止。
因此，我们可以从最高面额n开始，依次找出它的因子，再找出每个因子的因子，直到找到最低面额1为止，这样就可以快速计算出货币种类的数目。在找因子的过程中，可以使用从1到n的循环，判断每个数是否是n的因子来实现。
另外，可以利用一个变量count来记录已经找到的货币种类数目，每找到一个新的货币面额，就将count加1，最终输出count即可。
总之，这道编程题的亮点在于需要巧妙地利用数学知识和循环，快速计算出最多的货币种类数目。