蓝桥杯 ALGO-121 算法训练 猴子分苹果

算法训练 猴子分苹果  

时间限制:1.0s   内存限制:256.0MB

 

问题描述
  秋天到了,n只猴子采摘了一大堆苹果放到山洞里,约定第二天平分。这些猴子很崇拜猴王孙悟空,所以都想给他留一些苹果。第一只猴子悄悄来到山洞,把苹果平均分成n份,把剩下的m个苹果吃了,然后藏起来一份,最后把剩下的苹果重新合在一起。这些猴子依次悄悄来到山洞,都做同样的操作,恰好每次都剩下了m个苹果。第二天,这些猴子来到山洞,把剩下的苹果分成n分,巧了,还是剩下了m个。问,原来这些猴子至少采了多少个苹果。

 

输入格式
  两个整数,n m

 

输出格式
  一个整数,表示原来苹果的数目

 

样例输入
5 1

 

样例输出
15621

 

数据规模和约定
  0<m<n<9
 

分析:这题事实上是李政道博士在中国科技大学访问时曾对少年班的同学提出的一个问题。

现在假设猴子至少采了蓝桥杯 ALGO-121 算法训练 猴子分苹果个苹果,则第一只猴子操作后,剩余的苹果有蓝桥杯 ALGO-121 算法训练 猴子分苹果

类似地,第2只猴子操作后,还剩苹果蓝桥杯 ALGO-121 算法训练 猴子分苹果

……

一直这样下去,直到第蓝桥杯 ALGO-121 算法训练 猴子分苹果只猴子操作后,还剩苹果蓝桥杯 ALGO-121 算法训练 猴子分苹果

第二天,最后剩下的苹果满足蓝桥杯 ALGO-121 算法训练 猴子分苹果蓝桥杯 ALGO-121 算法训练 猴子分苹果为某一正数),即表明整除。

于是,倒推回去,可得

蓝桥杯 ALGO-121 算法训练 猴子分苹果

所以得

蓝桥杯 ALGO-121 算法训练 猴子分苹果

题目要求蓝桥杯 ALGO-121 算法训练 猴子分苹果“至少”是多少,则要使蓝桥杯 ALGO-121 算法训练 猴子分苹果,于是得

蓝桥杯 ALGO-121 算法训练 猴子分苹果

 

#include <stdio.h>

int pow(int a, int b)
{
    int ans = 1;
    for (int i = 1; i <= b; ++i)
        ans *= a;
    return ans;
}

int main()
{
    int n, m;

    scanf("%d %d", &n, &m);
    printf("%d", pow(n, n + 1) + (1 - n) * m);

    return 0;
}

 

蓝桥杯 ALGO-121 算法训练 猴子分苹果蓝桥杯 ALGO-121 算法训练 猴子分苹果 liulizhi1996 发布了186 篇原创文章 · 获赞 40 · 访问量 3万+ 私信 关注
上一篇:蓝桥算法训练 字符串合并 ALGO-233


下一篇:Algo 2: Asymptotic Order of Growth