时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 414 测试通过 : 34
比赛描述
夏天来了，宿舍里的蚊子越来越多了。L最近研发了一种环保型的灭蚊药水，但这种药水的效力会随着它的使用次数而降低。经过大量的测试和统计，发现这种药水的效力呈如下规律：若每次都使用M剂量的药水，则第一次使用时，能杀死M只蚊子，第二次使用时，只能杀死M/2只蚊子，第三次使用时，只能杀死M/3只蚊子，…，第N次使用时，只能杀死M/N只蚊子。L想知道在每次都使用M剂量药水的情况下，使用N次药水后一共能杀死多少只蚊子。为了方便统计，每一次杀死的蚊子数目以整数计，当不是一个整数时，则忽略小数点后面的数值。
例如，当使用药水的次数N为3， 每次使用的药水剂量M为5时，能杀死的蚊子总数为：5/1+5/2+5/3=5+2+1=8。
输入
输入含若干组测试数据，每组数据占一行。每一行有两个正整数，其中第一个数为每次使用的药水剂量M，第二个数为使用药水的次数N，(1<=M，N<=231-1)，两数之间用一个空格隔开。当输入一个负整数的时候表示输入数据结束。
输出
对应每一组测试数据，输出一个整数，表示使用N次药水能杀死的蚊子总数。一个整数占一行。
样例输入
5 3
3 5
1 1
-1
样例输出
8
5
1
就是求(M/1+M/2+M/3+cdots+M/N)的值，可以考虑到当分母足够大的时候会有(lfloor frac{M}{K} floor)很多相等，所以取一个分界点，大于分界点时使用枚举答案算个数，小于直接累加，效率很高。
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <math.h>
#include <bitset>
#include <ctype.h>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
int m,n;
int main()
{
while(true)
{
scanf("%d", &n);
if(n <= -1) break;
scanf("%d", &m);
if(m > n) m = n;
int rt = sqrt(n);
int base = n/m;
int en = m,st = n/(base+1);
LL ans = 0;
while(en > rt)
{
ans += base*(en-st);
en = st;
base++;
st = n/(base+1);
}
for(int i = 1; i <= en; i++)
ans += n/i;
printf("%I64d
", ans);
}
return 0;
}