Number Theory

001

for (int i = 2; i <= Math.sqrt(N); i++) {

    // QRP
    if (F[i] == 0)
        continue;

    // operation
    for (int j = i + i; j <= N; j = j + i) {
        F[j] = 0;
    }
}

N의 제곱근까지 수행

- QRP는 전 i의 operation으로 인해 변동된 것을 회수하는 것이다

for linear box

• 2의 배수부터 시작,
• N까지
• 시행 간격은 i

D/S test 피드백

• QRP가 j 문에 속해있지 않고, 바깥에 속해있음
• 뒤쪽 j는 i가 아닌, i+i부터 시작, j 시행간격은 i+i가 아닌 j+i임

 

-


002

// OEC
for (int i = M; i <= N; i++) {
    if (F[i] != 0)
        System.out.println(F[i]);
}

2가지 체

• 모든 field에 시행 후, 출력에서 거르는 경우(이번 경우)
• 구분된 field만 실행, 그대로 출력하는 경우

-


003

// Operating Almost-prime + Marker
int marker = 0;
for (int i = 2; i < 10000001; i++) {
    if (F[i] != 0) {
        long temp = F[i];
        while ((double)F[i] <= (double)Max / (double)temp) {
            if ((double)F[i] >= (double)Min / (double)temp) {
                marker++;
            }
            temp = temp*F[i];
        }
    }
}

- 전단계의 소수 검증에서 살아남는 것만 체크하면 됨
- while 내부의 if 로 조건 교집합

- 10^14는 long형마저 초과하므로, 10^7씩 나눠서 이항정리로 계산
- double wrapping 해주기
- 부등식의 양쪽에 F[i]를 쓸 수도 있으나, 2제곱 연산 후 3제곱 4제곱..도 들어가야 하므로 temp container에 담아 곱해가 며 쓴다


-


004

// EM : Palindrome checker
private static boolean isPalindrome(int target) {
    char[] temp = String.valueOf(target).toCharArray();
    int s = 0;
    int e = temp.length - 1;
    while (s < e) {
        if (temp[s] != temp[e])
            return false;
        s++;
        e--;
    }
    return true;
}

- Int를 String으로 Wrapping 후 char[] 로 쪼개기

팰린드롬 검증

• 포인터들이 양쪽에서 서서히 좁혀오다가
• 만약 짝수여서 중간에 수가 남지 않는다면 검증 통과
• 수가 남아서 s = e가 되는 경우여도 검증 통과

검증시 if의 모든 순간에서 살아남을 때만 true이고, ,false인 순간 하나만 있으면 판단 완료아므로 false로 시작한다


-

005

// Palindrome & Prime & Upper N -checker
int i = N;
while (true) {
    if (F[i] != 0) {
        int result = F[i];
        if (isPalindrome(result)) {
            System.out.println(result);
            break;
        }
    }
    i++;
}

- 전 단계 소수 검증에서 살아남는 것들만 체크
- N 이상은 그냥 N 이상부터 테스트 하면 된다

- int i = N; 은 시작을 얘기하는 것

 

While 구조

• 일단 모두 influx 시키고, 내부 Pipeline으로 거른다
• true와 if(boolean)-break 구조

-

006

// Setup
boolean[] checker = new boolean[(int) (Max - Min + 1)];

- (Max - Min + 1)은 capacity


007

-

// Operating non-square
for (long i = 2; i*i <= Max; i++) {

    long pow = i*i;
    long start_index = Min / pow;
    if (Min % pow != 0)
        start_index++;

    for (long j = start_index; pow*j <= Max; j++) {
        checker[(int) ((j*pow) - Min)] = true;
    }
}

 

 

// PRe
long result = 0;
for (long p = 2; p <= Math.sqrt(n); p++) {
    if (n % p == 0) {
        result = result - result/p;
        while (n % p == 0) {
            n /= p;
        }
    }
}

// OEC
if (n > 1)
    result = result - result / n;


System.out.println(result);

 

 

-

 

 

// EM : GCD
public static int GCD(int a, int b) {

    if (a < b) {
        int cont = a;
        a = b;
        b = cont;
    }

    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}

- operation 반복이 일어나고, b == 0 이라는 분기점에서 일들이 끝나게 된다 

- b가 0이란 뜻은, 직전 큰 수에서 작은수를 나눈게 나누어 떨어진다는 뜻이고

- 직전의 작은 수는 a이다

 

컴퓨터 논리 특성상, 판단을 하려면 변칙이 일어나는 그 끝 시행까지 가봐야 하지만, 그 직전 시행에서 원하는 값을 발견하게 된다

while도 마찬가지, 절벽 다음 시행에서 Lock이 걸려서 빠져나오게 됨

시행됨 + 시행안됨이 마지막

 

// ISC - L1~
Scanner sc = new Scanner(System.in);
long A = sc.nextLong();
long B = sc.nextLong();

// Setup
long result = GCD(A, B);

// OEc
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while (result > 0) {
    bw.write("1");
    result--;
}
bw.flush();
bw.close();

논지 : 동일 문자의 반복으로 수가 구성될때 (111111 등),  수의 길이를 나타내는 두 수의 GCD는, 원래 두 수의 GCD의 길이이다 

 

 

-

 

 

// External Class
class cNode {
    int b;
    int p;
    int q;

    public cNode(int b, int p, int q) {
        super();
        this.b = b;
        this.p = p;
        this.q = q;
    }

    public int getB() {
        return b;
    }
    public int getP() {
        return p;
    }
    public int getQ() {
        return q;
    }
}

비율 정보를 넣기 위해 ArrayList<>로 cNode를 작성한다

 

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    // setup
    static ArrayList<cNode>[] F;
    static long LCM;
    static boolean[] visited;
    static long[] D;

    public static void main(String[] args) throws Exception {

        // ISC - L1
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // L2~
        F = new ArrayList[N];
        visited = new boolean[N];
        D = new long[N];
        LCM = 1;
        for (int i = 0; i < N; i++) {
            F[i] = new ArrayList<cNode>();
        }
        for (int i = 0; i < N; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();
            F[a].add(new cNode(b, p, q));
            F[b].add(new cNode(a, q, p));
            LCM *= (p * q / GCD(p, q));
        }


        // Operating DFS + plate
        D[0] = LCM;
        DFS(0);
        long mgcd = D[0];
        for (int i = 1; i < N; i++) {
            mgcd = GCD(mgcd, D[i]);
        }

        // OEC
        for (int i = 0; i < N; i++) {
            System.out.print(D[i] / mgcd + " ");
        }
    }

    // External Module : DFS
    public static void DFS(int Node) {
        visited[Node] = true;
        for (cNode i : F[Node]) {
            int next = i.getB();
            if (!visited[next]) {
                D[next] = D[Node] * i.getQ() / i.getP();
                DFS(next);
            }
        }
    }
    // External Module : GCD
    public static long GCD(long a, long b) {
        if (b == 0)
            return a;
        else
            return GCD(b, a % b);
    }
}

// External Class
class cNode {
    int b;
    int p;
    int q;

    public cNode(int b, int p, int q) {
        super();
        this.b = b;
        this.p = p;
        this.q = q;
    }

    public int getB() {
        return b;
    }
    public int getP() {
        return p;
    }
    public int getQ() {
        return q;
    }
}