bzoj 1968: [Ahoi2005]COMMON 约数研究 (思维题)
1968: [Ahoi2005]COMMON 约数研究
Time Limit: 1 Sec Memory Limit: 64 MB Submit: 1997 Solved: 1508 [Submit][Status][Discuss]
Description
Input
只有一行一个整数 N（0 < N < 1000000）。
Output
只有一行输出，为整数M，即f(1)到f(N)的累加和。
Sample Input
3
Sample Output
5
HINT
Source
思路：如果跟着题目的意思走。。。求每个数的约束个数。。。复杂度是不资瓷的。。。
然而因为是求和，我们可以直接考虑，每个因子对答案的贡献。
容易知道，因子x对答案的贡献为n/x
x的范围为1..n
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月18日 星期五 21时46分37秒
4File Name :code/bzoj/1968.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int main()
34{
35 #ifndef ONLINE_JUDGE
36 freopen("code/in.txt","r",stdin);
37 #endif
38 LL n,ans=0;
39 cin>>n;
40 for ( LL i = 1 ; i <= n ; i++) ans = ans + n/i;
41 cout<<ans<<endl;
42
43 #ifndef ONLINE_JUDGE
44 fclose(stdin);
45 #endif
46 return 0;
47}