洛谷 P1403 [AHOI2005]约数研究

怎么会有这么水的省选题

一定是个签到题。

好歹它也是个省选题，独立做出要纪念一下

很容易发现在1~n中，i的因子数是n / i

那就枚举每一个i然后加起来就OK了

#include<cstdio>

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

int main()

{

    int n;

    scanf("%d", &n);

    long long ans = 0;

    _for(i, 1, n) ans += n / i;

    printf("%lld\n", ans);

    return 0;

}

不过好像还有更快的做法

因为很多n/i答案是一样的

所以可以把这些都加起来。

下列除法都是下取整

如果 n / i + 1 = n / j

则 j = n / (n / i)

这个结论非常有用！！！！

#include<cstdio>

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

int main()

{

	int n;

	scanf("%d", &n);

	long long ans = 0;

	_for(i, 1, n)

	{

		int j = n / (n / i);

		ans += (j - i + 1) * (n / i);

		i = j;

	}

	printf("%lld\n", ans);

	return 0;

}

巴特西

洛谷 P1403 [AHOI2005]约数研究

最新文章

热门文章