題目鏈接

---

時間限制(普通/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}\rfloor\)很多相等，所以取一個分界點，大于分界點時使用枚舉答案算個數，小于直接累加，效率很高。

#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\n", ans);}return 0; }

轉載于:https://www.cnblogs.com/Alruddy/p/7416284.html

總結

以上是生活随笔為你收集整理的NOJ 1186 灭蚊药水的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。