【题意】
回答第n个丑数是多少
丑数即为质因数只有2、3、5的数
【输入】
多次询问,询问以一个0结束
每次询问只有一个n
【输出】
回答每次询问
这个预处理一下前1500个丑数,回答的时候直接回答就好了
我挂了个堆来生成丑数,实际上没必要……
program poj1338; var all,tot,n,i,j,k:longint; ans:array [0..1501] of int64; heap:array [0..10001] of int64; procedure swap (var a,b:int64)inline; var i:int64; begin i:=a; a:=b; b:=i; end; procedure insert (now:int64);inline; var i:longint; begin inc(tot); heap[tot]:=now; i:=tot; while (i>1)and(heap[i]<heap[i div 2]) do begin swap(heap[i],heap[i div 2]); i:=i div 2; end; end; procedure delete;inline; var i:longint; begin if tot=1 then begin heap[1]:=heap[0]; dec(tot); exit; end; swap(heap[1],heap[tot]); heap[tot]:=heap[0]; dec(tot); i:=1; while (heap[i*2]<heap[i])or(heap[i*2+1]<heap[i]) do if heap[i*2]<heap[i*2+1] then begin swap(heap[i],heap[i*2]); i:=i*2; end else begin swap(heap[i],heap[i*2+1]); i:=i*2+1; end; end; begin fillchar(heap,sizeof(heap),63); tot:=0; ans[1]:=1; insert(2); insert(3); insert(5); for i:=2 to 1500 do begin while heap[1]=ans[i-1] do delete; ans[i]:=heap[1]; delete; insert(ans[i]*2); insert(ans[i]*3); insert(ans[i]*5); end; repeat read(n); if n=0 then break; writeln(ans[n]); until false; end.