Description

Input

输入文件仅包括一行，一个整数 N ( 2≤N≤231−1 )

Output

输出文件仅包括一行，一个整数，表示 F(n)

Sample Input

4

Sample Output

4

Data Constraint

Hint

对于 40% 的数据， 1≤N≤107
对于 60% 的数据， 1≤N≤108
对于 100% 的数据， 1≤N≤231−1

Solution

• 这题一眼就是一个数论题，只是处理方法有些与众不同

• 首先来看 60% 的数据： 1≤N≤108，O(N) 可以碾过

• 答案又显然是：

  (∑i=1n⌊Ni⌋)−n

• 即：

  ∑i=2n⌊Ni⌋

• 这样 60 分就解决了。但是 100 分的： 1≤N≤231−1 又怎么办呢?

• 观察可知，N 除以 i 下取整后，答案是有许多重复的，即一段一段的

• 那么把指针对到 N ，之后计算出下一段开头在哪儿，在累加整一段答案

• 这样打代码超短！可时间如何呢？

• 由于一个数的约数在数据范围内最多不过 105 个，时间复杂度接近 O((√N))

Code

#include<cstdio> using namespace std; int n,m,p; long long ans; int main() {scanf("%d",&n);for(m=n;m>1;m=p){int k=n/m;p=n/(k+1);ans+=k*(m-p);}printf("%lld",ans);return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 1219. Num的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。