1968: [Ahoi2005]COMMON 约数研究

Description

Input

只有一行一个整数 N（0 < N < 1000000）。

Output

只有一行输出，为整数M，即f(1)到f(N)的累加和。

Sample Input

    3

Sample Output

    5

 

 

题意：给定n，求1~n所有数约数个数和

考虑每个数对答案的贡献，x 对答案贡献为 n / x，复杂度O(n)

可以优化到O(√n)，有空再来填坑叭

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 8 using namespace std; 9 10 template 
            
              void read (tn & a) {11 tn x = 0, f = 1;12 char c = getchar();13 while (c < '0' || c > '9'){ if (c == '-') f = -1; c = getchar(); }14 while (c >= '0' && c <= '9'){ x = x * 10 + c - '0'; c = getchar(); }15 a = f == 1 ? x : -x;16 }17 18 int main() {19 int n;20 read(n);21 long long ans = 0;22 for (int i = 1; i <= n; ++i) {23 ans += (long long) (n / i);24 }25 printf("%lld\n", ans);26 return 0;27 }