某陈痴迷于pku的ACM题库,常常彻夜奋斗刷题.他最近的目标是在NOIP08到来之前刷进RANK[排名]200.

//----------^_^ encourage...-----------

pku对用户RANK的排列基于2个参数.Solved[通过的题数]和Submissions[提交次数].而二者之比就是AC Ratio[通过率].它反映一个用户的代码质量.话说某陈的AC Ratio就快降到60%了..郁闷ing.

最近某陈看到pku上有一串非常搞笑的用户,他们Solved的数量相同,而Submissions是从a到b的连续整数.某陈想要知道他们的AC Ratio之和.

当然,某陈要求的AC Ratio并不是完全如上所述[某陈:切..要是那样我自己就会写].他讨厌误差,于是他把Solved的数量用某种诡异的算法扩大了许多许多,变成一个整数n[数据保证0<n,但并不保证n<=b],他要求的AC Ratio,是n除以Submissions的商向上取整.

请帮某陈以他的方式计算那一串用户的AC Ratio之和. 

输入文件包含3个整数,依次为题目描述中的n,a,b.数据保证0<a<=b<2^31,0<n<2^31. 

输出文件应包含一个整数,是题目所要求的AC Ratio之和. 

18  8 10

7

[18/8]+[18/9]+[18/10]=3+2+2=7

[x]为实数x向上取整的值,例如 [5]=[4.03]=[4.92]=5 

 1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 using namespace std; 5 long long a,b,ans; 6 double c; 7 long long f(double n,long long a,long long b ) 8 { 9     if(ceil(n/a)==ceil(n/b)) return (b-a+1)*(ceil(n/a));10     long long mid=(a+b)/2;11     return f(n,a,mid)+f(n,mid+1,b);12 //    return ans;13 } 14 int main()15 {16     scanf("%lf%lld%lld",&c,&a,&b);17     printf("%lld",f(c,a,b));18     return 0;19 }

思路：分治的思想，如果 f(n, a, b) 表示该题的解，那么一定有 f(n, a, b) = f(n, a, (a + b) / 2) + f(n, (a + b) / 2 + 1, b)；容易知道：当 [n / a] = [n / b] 时，f(n, a, b) = (b - a + 1) * [n / a]，这比求和快一点。可知在b远大于n时，许多加数都为1。如 n = 5, b = 16, a = 4 时，可以用式 (2 + 1 * 6) + (1 * 6) 得解。但在n大于b时，对于任意 i 属于 [a, b]，[n / i] > 1。因此，最差情况时，该算法时间复杂度不如朴素算法。如果一次除法并且向上取整的时间复杂度为O(1)，那么该算法的时间复杂度为O(b-a)。暴力啥的那都弱爆了