[白俊BOJ]17427号-薬水の和2

📌 リファレンス
引き渡しアルゴリズム研究に関わる問題は19週目からBellogに記録される(18週前に復習してアップロードする予定)🤗) 他の個人が回答した基準やプログラマの質問は、自分が意味があると思っている部分だけをフィルタリングしてBellogに記録します.Bellogにアップロードされていない他の質問やコードを知りたい場合は、次のGithubでさらに確認できます.👀 ご来店ありがとうございます🙏
💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

code.plus問題セット:テスト符号化の準備-基礎|数学

17427号:約数の和2|問題ショートカット

回答（2022-02-02 WED）💻)

解の核心

自然数Aの約数の和は、Aの全約数を加算した値であり、f(A)で表される.
x以下の自然数yのすべてのf(y)値を加算した値をg(x)と表す.
👉 前述のように、問題のf(A)とg(X)を1つずつ実施すると、
(すなわち,1からNまでそれぞれf(A)を求め,これらの値を加算する.
タイムアウト発生
時間制限が0.5秒なので時間の管理もしっかりしていることにも気づきましたが.
好奇心で結果(?)そのまま実装されています(次のコードのコメントセクション)
案の定タイムアウト
したがって,以下のようにg(x)値から最初に見つけられるパターンで答えを求めるべきである.
ex)
1の約数 : 1
二の約数 : 1 2
三の約数 : 1   3
四の約数 : 1 2   4
5の約数 : 1       5
六の約数 : 1 2 3    6
七の約数 : 1           7
八の約数 : 1 2   4     8
9の約数 : 1   3         9
10の約数:1 2   5      10
そうごう
1*(10/1) + 2*(10/2) + 3*(10/3) + 4*(10/4) + 5*(10/5) + 6*(10/6) + 7*(10/7) + 8*(10/8) + 9*(10/9) + 10*(10/10)
= 1*10 + 2*5 + 3*3 + 4*2 + 5*2 + 6*1 + 7*1 + 8*1 + 9*1 + 10*1
= 87
👉 時間だけでなく、変数の資料型範囲も考慮しなければならない.
Nが1000000の場合、答えの値は822468118437です.
int範囲-24748648～2147483647を超える
(21億または10桁を超えるとint範囲を超えていると考えられる)
したがって、intではなくlong longとして答え変数を宣言する必要があります.

🚨 うっかり

上記で説明したように、答え変数はlong longで宣言されます.
出力フォーマットは"%lld"ではなく、"%d"でエラーが表示されます.
昨日に続いて出力フォーマットエラーが発生しました...ミスも実力😥
🔥 急いで食べないで、最後までまじめにしなさい.

🔽 コード(C+)

#include <iostream>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);

    long long answer = 0;
    for (int i=1; i<=N; i++) {
        answer += i*(N/i);
    }
    printf("%lld", answer);

    return 0;
}

/*
시간 초과 발생 코드

int f(int num) {
    int sum = 0;
    int squareRoot = (int)sqrt(num);
    for (int i=1; i<=squareRoot; i++) {
        if (num % i == 0) {
            sum += i;
            if (i*i != num) {
                sum += num / i;
            }
        }
    }
    return sum;
}

int main() {
    int N;
    scanf("%d", &N);

    int answer = 0;
    for (int i=1; i<=N; i++) {
        answer += f(i);
    }
    printf("%d", answer);

    return 0;
}
*/