BZOJ-1968

扫码查看

  

1968: [Ahoi2005]COMMON 约数研究

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 2308  Solved: 1768
[Submit][Status][Discuss]

Description

BZOJ-1968-LMLPHP

Input

只有一行一个整数 N(0 < N < 1000000)。

Output

只有一行输出,为整数M,即f(1)到f(N)的累加和。

Sample Input

3

Sample Output

5

HINT

 

Source

/*
* Author: lyucheng
* Created Time: 2017年05月14日 星期日 16时13分57秒
* File Name: /media/lyucheng/Work/ACM源代码/数学--数论/递推找规律打表/BZOJ-1968.cpp
*/
/* 题意:定义了一种运算f(n)为n的因子个数,然后让你求1-n的f(n)的和
*
* 思路:进行离线打表
*
* 错误:考虑的太浅了,正常打标跑了2000ms+,应该反过来想,打欧拉函数线性筛欧拉函数,然后减去就行了
*
* 还是错误:上面的想法不对,这样筛输出来的只是和n不互质的数,但并不是因子
* 换个思路不用于处理,n/i表示比n小的数中i的倍数有多少,这样O(n)就可以处理出来
* */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
#define MAXN 1000005
#define LL long long
using namespace std;
int n;
int main(int argc, char* argv[])
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout;
while(scanf("%d",&n)!=EOF){
LL res=;
for(int i=;i<=n;i++){
res+=n/i;
}
printf("%lld\n",res);
}
return ;
}
04-26 15:04
查看更多