Description

Input

輸入文件僅包括一行，一個(gè)整數(shù) N ( 2≤N≤231?1 )

Output

輸出文件僅包括一行，一個(gè)整數(shù)，表示 F(n)

Sample Input

4

Sample Output

4

Data Constraint

Hint

對(duì)于 40% 的數(shù)據(jù)， 1≤N≤107
對(duì)于 60% 的數(shù)據(jù)， 1≤N≤108
對(duì)于 100% 的數(shù)據(jù)， 1≤N≤231?1

Solution

• 這題一眼就是一個(gè)數(shù)論題，只是處理方法有些與眾不同

• 首先來看 60% 的數(shù)據(jù)： 1≤N≤108，O(N) 可以碾過

• 答案又顯然是：

  (∑i=1n?Ni?)?n

• 即：

  ∑i=2n?Ni?

• 這樣 60 分就解決了。但是 100 分的： 1≤N≤231?1 又怎么辦呢?

• 觀察可知，N 除以 i 下取整后，答案是有許多重復(fù)的，即一段一段的

• 那么把指針對(duì)到 N ，之后計(jì)算出下一段開頭在哪兒，在累加整一段答案

• 這樣打代碼超短！可時(shí)間如何呢？

• 由于一個(gè)數(shù)的約數(shù)在數(shù)據(jù)范圍內(nèi)最多不過 105 個(gè)，時(shí)間復(fù)雜度接近 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; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 1219. Num的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。