PKU 2668 Defending Castle
http://poj.org/problem?id=2668
ある整数n,dが与えられる。
この時、Σ(1<=i<=n) roundup(d/i) を計算しろというような問題。
sqrt(d)くらいの解法です。
バグバグになったので、出来るだけWAを減らそうと思い、愚直な方法と出力を比べながらデバッグしました。
main(){ ll n,d; while(cin>>d>>n,n|d){ ll ans=0; ll nd=0; for(int i=1;;++i){ if(i>n)break; ll td=(d+i-1)/i; if(nd==td)break; nd=(d+td-1)/td; if(nd==td)ans-=td; ans+=td; ll e,s; s=(d-1)/nd+1; if(s>n)continue; if(nd==1)e=max(s,n+1); else e=min((d-1)/(nd-1)+1,n+1); ans+=(e-s)*nd; if(nd>=td)break; } cout<<ans<<endl; } }