数学

薬の時間の複雑さを求めます
nのすべての約数を求める時間複雑度はO(√N)である.
1からsqrt(N)まですべての自然数に分けられるからです.
1037号約数
📌質問する
正数AをNの真約数にするには,NはAの倍数であり,Aは1とNではない.任意の数Nのすべての真約数が与えられた場合、Nを求めるプログラムを作成してください.
ex A=24の場合、本物の薬液Aは2,3,4,6,8,12
入力
第1行はNの真約数の個数を与える.この数は50以下の自然数です.2行目はNの真約数を与える.10,000,000以下、2以上の自然数は、繰り返しません.
📄しゅつりょく
1行目にNを出力します.Nは常に32ビットの整数で表すことができる.
👀例
入力
2
4 2
しゅつりょく
8
時間の複雑さ
最小値と最大値の積を求めればいいです.
nの真の約数がM個である場合,時間複雑度はO(M)である.
🌴 Code

package math;

import java.util.Scanner;

public class no1037_약수 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int [] num = new int[count];

        for (int i=0;i<count;i++){
            num[i] = sc.nextInt();
        }
        int max = num[0];
        int min = num[0];
        for (int i=1;i<count;i++){
            max = Math.max(max,num[i]);
            min = Math.min(min,num[i]);
        }
       System.out.println(max*min);
    }
}

17427薬水フィット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)を求める.
時間制限0.5秒
入力
第1行は自然数N(1≦N≦1000000)を与える.
📄しゅつりょく
1行目にg(N)を出力する.
👀例
入出力1124108777040651000082256014
時間の複雑さ
f(A)の時間的複雑度O(√A)
g(N) = N x O(√N) = O(N√N)
Nの範囲は(1≦N≦1000000)
N√N≦100000 x 1000=10億=10秒.
時間が0.5秒に制限されているので、上記の解答はxです.
「排水」の考え方で「薬物水に反対する」問題を解決する.
n以下の自然数のうち、1の倍数の個数(1は約数)はN/1個
n以下の自然数では、2の倍数(2は約数)がN/2個
n以下の自然数のうち、3の倍数の個数(3は約数)はN/3個である
...
n以下の自然数において、iの倍数(iは約数)はn/i個である
時間複雑度O(1)X N=O(N)
🌴 Code

package math.no17427약수의합2;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        long g = 0; // ❗ 데이터타입 주의 int는 약 21억까지만 가능

         for (int i=1;i<=a;i++) g += a/i * i;

        System.out.println(g);
    }
}

17425薬水フィット
📌質問する
上の薬水の和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)を求める.
タイムアウト1秒
入力
第1行は、試験例の個数T(1≦T≦100000)を与える.2行目から、試験例は1行1個、自然数N(1≦N≦100000)である.
📄しゅつりょく
各試験例は、行ごとにg(N)を出力する.
👀例
入出力5121070010000148706582256014
質問に答える
g(N) = O(N)
O(TN)=1億2千万円(千億円)を超え、1秒(1億円)を超えた.
💡 テストケースの問題を解決する際に注意すべき事項
ex Nが100または1000であっても、24の薬水を得る.これは,入力が影響を受けず,一定の値を有することを示す.毎回不変の値を求めるのは効率的ではありません!
一度だけ助けて、それから利用します.一度に取得し、再使用
前述の問題で用いた「薬水逆倍数」の考え方を用いて,薬水の和を事前に求めた.
🌴 Code
スキャナとシステム.out.印刷もタイムアウト...

package math.n17425_약수의합;

import java.io.*;

public class Main {
    static final int MAX = 1000000;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long [] data = new long [MAX+1];

        //모든 수가 1을 약수로 가짐
        for (int i=1;i<=MAX;i++) data[i] = 1;

        //⏳ O(NlogN) ❗ ❗ ❗ 
        for (int i=2;i<=MAX;i++){ //i를 약수로 가지면 data에 넣어주기
            for (int j=1; i*j<=MAX;j++) {
            data[i*j] += i; //index는 약수를 가지는 수를 의미
            }
        }

        //⏳ O(N)
        long [] g = new long[MAX+1];
        for (int i=1;i<=MAX;i++){
            g[i] = g[i-1] + data[i]; // ❗ 배열 초기화 디폴트 값은 0
        }
/********************여기까지가 미리 한번에 구해둔 것 **********************/

        //⏳ O(T)
        int t = Integer.parseInt(bf.readLine()); // readLine 메소드는 String 값만 받을 수 있다.
        while (t-- >0){
            int n = Integer.parseInt(bf.readLine());
            bw.write(g[n]+"\n");// ❗  write는 아스키 코드에 따른 char형 값이 출력된다.
            // 그러나 i와 개행 처리 문자열 "\n" 을 더하면 String 으로 자동 형변환 되기 때문에
            // 저장되어 있는 int 값 그대로 출력이 가능하다. "\n" 안하면 에러생겼어서 당황했었음 
        }
        bw.flush();
        bw.close(); // ❗ 꼭꼭 close 해주어야 함

        //⏳ 총 시간 복잡도 O(NlogN+N+T) = O(NlogN+T)
    }
}

時間の複雑さ
配列に自然数Aの約数の和を加え,インデックスは自然数Aである.
data[A] = f(A)
時間複雑度:O(Nx?)

データの時間的複雑さ
i=2, j= 1~N/2 -> N/2
i=3, j= 1~N/3 -> N/3
...
i=N, j= 1~N/N -> N/N
=> N/2 + N/3 ...+ N/(N-1) + N/N
=> O(NlogN)

🔔 1+1/2+1/3 ... +1/N≤ logN+1
表最終O(NlogN+T)
=6000000+100000=610万<1億で、時間の制限を満たしています.