약수의 합 2

문제 링크
난이도 : 실버 2

문제 내용

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

문제 분석

g(n)은 n보다 작거나 같은 모든 자연수의 모든 약수를 더한 것.

작성한 코드

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    int n;
    vector<int> fs;
    scanf("%d", &n);
    for(int i = 0; i <= n; i++) fs.push_back(0);
    
    for(int i = 1; i <= n; i++){
        for(int j = i; j<=n; j+=i){
            fs[j] += i;
        }
    }
    for(int i = 1; i <= n; i++){
        printf("%d\\n", fs[i]);
    }
    
    
    int gn = accumulate(fs.begin(), fs.end(), 0);
    printf("%d", gn);
}

배열로 저장해서 할려고 했는데 실패함.. 이유를 못찾겠음

다른 블로그 글 분석하니까 규칙성을 찾으라길래 찾아봄

g(n)에서 특정 숫자 i가 나오는 횟수는 n/i 번이더라!

#include<bits/stdc++.h>
#include<iostream>
 
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    long long gn = 0; 
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        gn += (n / i) * i;
    }
    cout << gn << endl;
}

이상한점… 입력을 iostream으로 안받고 scanf으로 받았을때는 똑같은 코드인데 실패로 떴음.. 이해안감

우수 코드 분석

#include <iostream>
#include <bits/stdc++.h>
using namespace std; 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    long long ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int temp = n / i;
        temp *= i;
        ans += temp;
    }
    cout << ans;
}

이분 말고도 다른분들도 비슷하게 짜셨는데 다들 iostream으로 받아오신거 보고 나도 써봄..

앞으로 뭔가 안된다 싶으면 입력 다르게 받아봐야할듯