https://www.acmicpc.net/problem/1188
μ½λ
import java.util.Scanner;
public class Main {
public static int GCD(int a, int b) {
if(b == 0) return a;
return GCD(b, a%b);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int M = scan.nextInt();
System.out.println(M - GCD(N, M));
scan.close();
}
}
νμ΄
μ΄ λ¬Έμ λ νμ΄λ§ μλ©΄ μ λ§ κ°λ¨νμ§λ§,, κ·Έ νμ΄λ₯Ό μκ°ν΄λ΄λκ² μ΄λ ΅λ€.
μ²μμ νλλ Nκ³Ό Mμ κΈ°μ€μΌλ‘ N>M , N==M , N<M μΌλ‘ λλμ΄μ νμλλ°,
νλ€λ³΄λκΉ λ μκ° μλ‘ λ°°μμΈμ§ μλμ§μ λν΄ κ΄λ ¨μ΄ μμλ€.
λν μμμ§λ₯Ό μ΄μ΄λΆμ΄λ λ°©μμ λν΄ μκ°μ λͺ»νμλ€.
κ°―μμ μκ΄μμ΄ νλ‘ κ°λ€μ μμμ§λ₯Ό N/M κ° λ§νΌ κ°μ Έκ°λ€.
N = 3 , M = 5 ---> 1λͺ λΉ κ°μ§λ μμμ§μ μ = 3/5 --- νμν μΉΌμ§ : 4ν
N = 4 , M = 5 ---> 1λͺ λΉ κ°μ§λ μμμ§μ μ = 4/5 --- νμν μΉΌμ§ : 4ν
N = 6 , M = 3 ---> 1λͺ λΉ κ°μ§λ μμμ§μ μ = 6/3 --- νμν μΉΌμ§ : 0ν
μ¬κΈ°μ, μμμ§ Nκ°λ₯Ό μ΄μ΄λΆμ΄λ©΄ μΉΌμ§μ (M-1)λ²μ΄ νμνλ€.
νμ§λ§ λ§μ§λ§κ³Ό κ°μ΄, Nμ΄ Mμ λ°°μμΌκ²½μ° μΉΌμ§μ μ ν νμκ° μλ€.
μ¦ μ΅μν M - GCD(N, M)λ²μ μΉΌμ§μ΄ νμνλ€.
(μ΅μ μ κ²½μ° GCD(N, M) = 1 ---> (M-1)λ²μ μΉΌμ§)
'Algorithm' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Codeforces] 1080A: Petya and Origami (0) | 2020.04.09 |
---|---|
[λ°±μ€] 14502λ²: μ°κ΅¬μ(DFS, BFS, μμ νμ) (0) | 2020.04.08 |
[Codeforces] 1316A: Grade Allocation (0) | 2020.04.07 |
[λ°±μ€] 10709λ²: κΈ°μμΊμ€ν°(ꡬν) (0) | 2020.04.07 |
[λ°±μ€] 1021λ²: νμ νλ ν (0) | 2020.04.07 |
λκΈ