本文主要是介绍uva 10726 - Coco Monkey(数论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 10726 - Coco Monkey
题目大意：n个人，m只猴子，l和r，表示上下限。找出l~r之间有几个数满足题目要求。
s即为由满足要求的数，在题目中表示有s个椰子，n个人说好第二天将椰子平分，但是午夜的时候，一个人偷偷爬起来，将椰子分成n份，并且剩了m个，就将m个拿给了猴子，并且自己藏起来一份；紧接着第2个人，第3个人都按照相同的方法一直到最后一个人；然后第二天，剩下的椰子刚好平分给这n个人，这回没有猴子的了。
解题思路：这题主要是找到满足的s的个数，a数组表示说第i个人时的椰子个数a[i]=s* a[i+1]/(s-1) + m.
这种形式刚好可以转化成等比公式，假设bi = ai + k，
那么a[i] + k = (s/(s-1)) * (a[i+1] + k), 得k = m*(s-1);
这样就可以枚举最后一项个值，然后通过式子求出s，判断s是否在区间[l,r]上即可。
#include <cstdio>
#include <cstring>
#include <cmath>typedef long long ll;
ll s, m, l, r;int solve () {if (log2(s-1) * s > 32)return 0;ll t = s * (s - 1);ll d = m * (s - 1);ll p = pow(s, s);ll q = pow(s-1, s);int ans = 0;for (ll i = t; i <= 1e8; i += t) {ll u = (i + d) * p;if (u % q)continue;u = u / q - d;if (u > r) break;if (u >= l)ans++;}return ans;
}int main () {int cas;scanf("%d", &cas);for (int i = 1; i <= cas; i++) {scanf("%lld%lld%lld%lld", &s, &m, &l, &r);printf("Case %d: %d\n", i, solve());}return 0;
}
这篇关于uva 10726 - Coco Monkey(数论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
