2011-09-04 23:26:59Morris
d087. 107 - The Cat in the Hat
d087. 107 - The Cat in the Hat
作法 : 窮舉 n
/**********************************************************************************/
/* Problem: d087 "107 - The Cat in the Hat" from Uva ACM 107 */
/* Language: C */
/* Result: AC (2ms, 216KB) on ZeroJudge */
/* Author: morris1028 at 2011-09-04 23:24:02 */
/**********************************************************************************/
#include<stdio.h>
#include<math.h>
long long test(int n, int nk, int h) {
long long tmp, k;
tmp = n, k = 1;
if(h%(n+1)) return 0;
h /= n+1;
while(tmp*n <= nk) {
tmp *= n, k++;
if(h == 1 && tmp == nk)
return k;
if(h%(n+1)) return 0;
h /= n+1;
}
if(tmp == nk && h == 1)
return k;
return 0;
}
main() {
int h, nk, i;
long long t;
while(scanf("%d %d", &h, &nk) == 2) {
if(h == 0 && nk == 0)
break;
if(h == 1) {
printf("0 %d\n", nk);
continue;
}
int sq = (int)sqrt(nk);
long long tmp, k;
for(i = 1; i <= sq; i++) {
if(nk%i == 0) {
if(test(i, nk, h)) {
t = test(i, nk, h)-1;
if(i == 1)
printf("%lld %d\n", t, h*(i+1)-1);
else
printf("%d %d\n", (nk-1)/(i-1), h*(i+1) - nk*i);
break;
}
if(test(nk/i, nk, h)) {
printf("%d %d\n", (nk-1)/(nk/i-1), h*(nk/i+1) - nk*(nk/i));
break;
}
}
}
}
return 0;
}
內容 ：
一隻神奇聰明貓走進了一間亂七八糟的房間，他 不想自己動手收拾，他決定要找幫手來工作。於是他從他的帽子中變出了N隻小貓來幫他（變出來的貓，高度為原來貓的 1/(N+1) ）。這些小貓也有帽子，所以每一隻小貓又從他的帽子中變出N隻小小貓來幫他。如此一直下去，直到這些小小小....貓小到不能再小（高度＝1），他們的帽 子無法再變出更小的貓來幫忙，而這些最小的貓只得動手打掃房間。注意：所有貓的高度都是正整數。
在這個問題中，給你一開始那隻貓的高度，以及最後動手工作的貓的數目（也就是高度為1的貓的數目）。要請你求出有多少隻貓是沒有在工作的，以及所有貓的高度的總和。
輸入說明
：
每組測試資料一列，有2個正整數分別代表一開始那隻貓的高度，以及最後動手工作的貓的數目。0 0代表輸入結束。
輸出說明
：
每組測試資料輸出一列，包含2個正整數分別代表有多少隻貓是沒有在工作的，以及所有貓的高度的總和。
範例輸入 ：
216 125 5764801 1679616 64 1 0 0
範例輸出 ：
31 671 335923 30275911 6 127
提示
：
* 中文翻譯：Lucky 貓
出處
：
Uva ACM 107
(管理：MAPLEWING)
作法 : 窮舉 n
/**********************************************************************************/
/* Problem: d087 "107 - The Cat in the Hat" from Uva ACM 107 */
/* Language: C */
/* Result: AC (2ms, 216KB) on ZeroJudge */
/* Author: morris1028 at 2011-09-04 23:24:02 */
/**********************************************************************************/
#include<stdio.h>
#include<math.h>
long long test(int n, int nk, int h) {
long long tmp, k;
tmp = n, k = 1;
if(h%(n+1)) return 0;
h /= n+1;
while(tmp*n <= nk) {
tmp *= n, k++;
if(h == 1 && tmp == nk)
return k;
if(h%(n+1)) return 0;
h /= n+1;
}
if(tmp == nk && h == 1)
return k;
return 0;
}
main() {
int h, nk, i;
long long t;
while(scanf("%d %d", &h, &nk) == 2) {
if(h == 0 && nk == 0)
break;
if(h == 1) {
printf("0 %d\n", nk);
continue;
}
int sq = (int)sqrt(nk);
long long tmp, k;
for(i = 1; i <= sq; i++) {
if(nk%i == 0) {
if(test(i, nk, h)) {
t = test(i, nk, h)-1;
if(i == 1)
printf("%lld %d\n", t, h*(i+1)-1);
else
printf("%d %d\n", (nk-1)/(i-1), h*(i+1) - nk*i);
break;
}
if(test(nk/i, nk, h)) {
printf("%d %d\n", (nk-1)/(nk/i-1), h*(nk/i+1) - nk*(nk/i));
break;
}
}
}
}
return 0;
}