題意:
求前n項的n/i 的和 隻取整數部分
暴力肯定逾時。。。然後 。。。現在的人真聰明。。。我真蠢
覺得還是别人的題意比較清晰
比如n=100的話,i=4時n/i等于25,i=5時n/i等于20,于是在大于20到小于等于25内的5個數字j都有n/j等于4,然後ans+=4*5
是以我們可以在小于等于根号n的範圍内枚舉i,ans+=n/i,然後ans+=(n/(i)-n/(i+1))*i,這樣分段加起來
但是又重複的部分。。
即 令m = sqrt(n), 如果n / m == m 則n / (m+1) == m-1 是以在循環進行到最後一項 即m時 n/i - n/(i+1)等于 1 是以在執行 res += (n/i - n/(i+1))*i時(即 res += 1*m 時)多加了一個m
是以要最後判斷一下 減去
例如 1、2、3、4、5、6、7、8、9、10
sqrt(10)= 3
是以 最後應該是1個10 1個5 1個3 2個2 5個1
但在循環執行到i=3 時 多加了一個3
若還不懂 具體看看代碼 自己寫一下
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define maxn 100009
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int LL_INF = 0x7fffffffffffffff,INF = 0x3f3f3f3f;
int main()
{
int T;
cin>> T;
int cnt = 0;
while(T--)
{
LL n, res = 0;
cin>> n;
LL m = sqrt(n);
for(LL i=1; i<=m; i++)
{
res += n/(double)i;
res += (n/i - n/(i+1)) * i;
}
if(n/m == m)
res -= m;
printf("Case %d: %lld\n",++cnt,res);
}
return 0;
}
轉載于:https://www.cnblogs.com/WTSRUVF/p/9184774.html