[ACM ] 107 tle
( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
( 未必需要依照此格式，文章條理清楚即可 )
題號：107 http://163.32.78.107/homework/q107.htm
遇到的問題：不知為何在UVA永遠tle，目標是只"少部分"更改以下code後得到AC。
有問題的code： (用C語言)
#include <stdio.h>
#include <math.h>
int main()
{
long int h,nw,N,A,x,sum,temp,a,b,L; //h:初貓身高，nw:最後工作貓數
double hs; //N:一次分裂N隻，hs:所有貓總身高
//概念：N的x次方=nw，(N+1)的x次方=h。所以N為nw因數，N+1為h的因數。
while(scanf("%ld %ld",&h,&nw)==2)
{
if(h==0 && nw==0) return 0;
if(h==1 && nw==1)
{
printf("0 1");
}
if(h!=1 && nw==1) //對付nw為1的測資
{
x=0; temp=h; L=0;
while(L==0)
{
temp/=2;
x++;
if(temp==1) L=1;
}
sum=1; hs=0;
while(sum<=h)
{
hs+=sum;
sum*=2;
}
printf("%ld %.0lf",x,hs);
}
//開始對付一般測資
L=0;
for(N=2;L==0&&nw!=1;N++) //從2開始找nw的因數，找到的因數N須滿足N^x=nw...
{ //也得滿足(N+1)^x=h;
if(N>sqrt(nw)) N=nw; //若直到(N=nw開根號)還找不到符合兩等式條件...
//讓N直接=nw。
if(nw%N==0)
{
temp=nw; //temp代替nw
while(temp%N==0&&L==0)
{
temp/=N;
if(temp==1) //temp一直除N直到變為1，表示N^x=temp=nw
{
L=1;
A=N+1; temp=h; //讓A=N+1，temp改為代替h
while(L==1) //檢查N+1是否滿足(N+1)^x=h
{
if(temp%A!=0) L=0;
temp/=A;
if(temp==1) L=2; //完全滿足了！
}
}
}
}
if(L==2)
{
sum=0;
for(a=1;a<nw;a*=N) sum+=a; //計算有幾隻沒工作
hs=0;
for(a=1,b=nw;a<=h;a*=A,b/=N) //計算總身高
{
hs+=a*b;
if(a==h) break;
}
printf("%ld %.0lf",sum,hs);
}
}
printf("\n");
}
return 0;
}
補充說明：某巨大測資(2147483647,2147483646)我也解決了，
用"執行"一次跑13筆測資，也才花一秒左右。
搞不懂UVA到底用了什奇怪測資，可以算到超過三秒...
懇請各位大大幫忙了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.221.175
※ 編輯: morris0117 來自: 140.123.221.175 (03/14 16:07)
推
03/14 17:01, , 1F
03/14 17:01, 1F
→
03/14 19:33, , 2F
03/14 19:33, 2F
→
03/14 19:34, , 3F
03/14 19:34, 3F
→
03/14 19:44, , 4F
03/14 19:44, 4F
→
03/14 22:29, , 5F
03/14 22:29, 5F