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;
}