[UVA][math] 10493 - Cats, with or without Hats
Problem BCats, with or without Hats Input: standard input
Problemsetter: K M Hasan, Member of Elite Problemsetters' Panel |
題目描述：
如果一隻貓有戴帽子，則帽子裡面會有 N 隻小貓，類推下去，會有一堆小小貓。
然後整個只會有 M 隻沒有戴帽子，問有幾隻貓。
題目解法：
當作一棵 N way tree(就是每個節點的分支 N)
設答案有 S 隻貓，葉節點有 M 個，推到內節點有 S-M 個
則由於是個長滿的樹，邊的個數會等於 (S-M)*N。
由於樹的節點個數 = 邊的個數+1，S = (S-M)*N+1
S = (M*N-1)/(N-1)
當 M = 1, N = 1 多組解
int main() {
long long n, m;
while(scanf("%lld %lld", &n, &m) == 2) {
if(n == 0) break;
printf("%lld %lld ", n, m);
if(n == 1 && m == 1)
puts("Multiple");
else if(n == 1 || (n*m-1)%(n-1))
puts("Impossible");
else
printf("%lld\n", (n*m-1)/(n-1));
}
return 0;
}