UVa10726 & UVa616 Coco Monkey & Coconuts, Revisited(数列递推)

好像有个视频介绍了这个水手与猴子与椰子的奇怪的数学问题,有兴趣的同学可以去看一看:Monkeys and Coconuts

然后回归到这2个以此为背景的题目,首先可以观察题目给出的表格:

有$S$个水手,$M$个猴子,设最后一轮留下来的椰子数为$a(1)$,那么有$a(1)=a(2)-\frac{a(2)-M}{s}-M$,反过来有$a(2)=a(1)\times \frac{s}{s-1} +M$,也就是$a(i)=a({i-1})\times \frac{s}{s-1} +M$。

由此想到经典的求等比数列递推的方法:设$b(i)=a(i+k)$,然后因为公比$q= \frac{s}{s-1}$,所以设$b(i)=q \times b({i-1})$,有$a(i)+k=\frac{s}{s-1} \times (a({i-1})+k)$,划开有$k\times \frac{s}{s-1} -k=M$,得$k=M \times (s-1)$。

由于有$b(i)=b({i-1}) \times q$,$q=\frac{s}{s-1}$,于是$S$个人以后有$b({s+1})= {(\frac{s}{s-1})}^s \times (a(1)+M\times (s-1))$,由于
$$b(i)=a(i)+k,k=M\times (s-1)$$,有$$a(s+1)+M \times (s-1) = {\frac{s}{s-1}}^s \times (a(1)+M \times (s-1))$$,我们想到枚举$a(1)$求解,而$a(1)$一定整除$s$和$s-1$(因为最后一轮要留下$s-1$份,而最后平分了$s$个人),所以枚举$a(1)$可以求得所有的符合条件的椰子数。

那么对于反问题,给定椰子树求最大人数怎么求解呢?从大到小枚举按幂连乘后在$long ~long$范围内的可行人数,输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
//UVa10726
using namespace std;
typedef long long ll;
ll quickpow(ll x,ll k)
{
ll res=1;
while(k>0)
{
if(k&1) res=res*x;
x=x*x;
k>>=1;
}
return res;
}
ll s,m,l,r;
int main()
{
int kas;
scanf("%d",&kas);
for(int z=0;z<kas;z++)
{
scanf("%lld%lld%lld%lld",&s,&m,&l,&r);
ll hcm=(s-1)*s;
ll ss=quickpow(s,s);
ll del=quickpow(s-1,s);
ll pl=m*(s-1);
ll cnt=0;
for(ll i=hcm;i<=1e8;i+=hcm)
{
ll now=(i+pl)*ss;
if(now%del!=0) continue;
now=now/del;
now=now-pl;
if(now>=l && now<=r) cnt++;
}
printf("Case %d: %lld\n",z+1,cnt);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
//UVa616
using namespace std;
typedef long long ll;
ll qkpw(ll x,ll k)
{
ll res=1;
while(k>0)
{
if(k&1) res=res*x;
x=x*x;
k=k/2;
}
return res;
}
int main()
{
ll s;
while(scanf("%lld",&s)==1)
{
if(s<0) break;
if(s==0) {printf("0 coconuts, no solution\n");continue;}
bool flag=false;
printf("%lld coconuts, ",s);
for(ll i=12;i>1;i--)
{
ll now=s+(i-1);
ll ss=qkpw(i,i);
ll s1=qkpw(i-1,i);
now=now*s1;
if(now%ss!=0) continue;
now=now/ss;
now=now-(i-1);
if(now<0) continue;
if(now==0 || (now%(i-1)==0 && now%i==0)) {
flag=true;printf("%lld people and 1 monkey\n",i);break;
}
}
if(!flag) printf("no solution\n");
}
return 0;
}