P1403 [AHOI2005]約數研究

題目描述

科學家們在Samuel星球上的探險得到了豐富的能源儲備，這使得空間站中大型電腦“Samuel II”的長時間運算成為了可能。由於在去年一年的辛苦工作取得了不錯的成績，小聯被允許用“Samuel II”進行數學研究。

小聯最近在研究和約數有關的問題，他統計每個正數N的約數的個數，並以f(N)來表示。例如12的約數有1、2、3、4、6、12。因此f(12)=6。下表給出了一些f(N)的取值：

f(n)表示n的約數個數，現在給出n，要求求出f(1)到f(n)的總和。

輸入輸出格式

輸入一行，一個整數n

輸出一個整數，表示總和

輸入輸出樣例

3

5

說明

【數據範圍】

20%N<=5000

100%N<=1000000

這題有點類似於篩法求素數

我們可以這樣想

一個數的倍數的約數中，一定這個數

=.=

那就簡單了，按照篩素數的方法暴力篩就可以

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=1000001;
 7 int num[MAXN];
 8 int main()
 9 {
10     int n;
11     scanf("%d",&n);
12     for(int i=1;i<=n;i++)
13     {
14         for(int j=i;j<=n;j+=i)
15         {
16             num[j]++;
17         }
18     }
19     int ans=0;
20     for(int i=1;i<=n;i++)
21         ans=ans+num[i];
22     printf("%d",ans);
23     return 0;
24 }