bzoj1968【AHOI2005】COMMON 约数研究

Description

Input

Output

Sample Input

Sample Output

HINT

Source

直接求每个数的因数个数是比较麻烦的，我们可以换一个角度考虑。对于每个数i，在1到n的范围内有多少个数是它的倍数？答案显然是n/i。于是最终的答案就是∑(n/i)。

#include<iostream>
#include<cstdio>
using namespace std;
int n,ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) ans+=n/i;
	printf("%d\n",ans);
}

bzoj1968【AHOI2005】COMMON 约数研究

原文：http://blog.csdn.net/aarongzk/article/details/50647495