将原来所有的的i按照d/i上取整=k的划分为各个区间[next,now),这区间里的ans值就等于(now-next)*k
初始now=n+1,k=1,然后每次next就等于d/i,k依次递增,实际上,不是每一个k的next和now所指代的区间都有意义,即next<now,所以,每当遇到一个这种没有意义的next和now时,就通过d/(now-1)上取整找到新的k,这样就可以大大节省时间。
View Code
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 int main() 7 { 8 long long d,n; 9 while(scanf("%lld%lld",&d,&n))10 {11 if(n==0&&d==0)12 break;13 long long ans=0;14 long long now=n+1,k=1,next;15 while(now>1)16 {17 next=d/k+(d%k!=0);18 if(now<=next)19 {20 next=now-1;21 k=d/next+(d%next!=0);22 }23 else24 ans+=(now-next)*k,k++,now=next;25 }26 printf("%lld\n",ans);27 }28 return 0;29 }