UVa 616 - Coconuts, Revisited

链接

传送门

题意

有\(n\)个椰子，一群人和一只猴子，这些人要平分椰子，第一个人在第一天晚上把椰子平分后剩1个给了猴子，然后拿走了自己的一份，其他的人也都这样做了。最后椰子正好平分，没有猴子的。输出满足要求的最大人数。

思路

从枚举\(sqrt(n)\)开始枚举是否可行。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long LL;
const int maxn = 55;
int a[maxn];

bool check(int n, int p) {
  for (int i = 0; i < p; ++i) {
    if (n % p == 1) {
      n = n / p * (p - 1);
    } else {
      return false;
    }
  }
  return n % p == 0;
}

int main() {
  int n;
  while (~scanf("%d", &n) && n >= 0) {
    printf("%d coconuts, ", n);
    bool ok = false;
    for (int i = sqrt(n) + 1; i > 1; --i) {
      if ((n - 1) % i == 0 && check(n, i)) {
        printf("%d people and 1 monkey\n", i);
        ok = true;
        break;
      }
    }
    if (!ok) {
      puts("no solution");
    }
  }
  return 0;
}