n,m이 매우 클 때 (a1a2a3...an)/(b1b2b3...bm) 분수를 계산하는 마법같은 방법

28828번: Упражнения в умножении (acmicpc.net)  $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}}$과 $10^{6}$ 이하로 차이나는 정수를 구하는 문제 n,m이 $10^{5}$까지이고, $a_{i}, b_{i}$가 $10^{9}$이라 단순하게 곱하고 나누면 시간초과가 난다 v1 = 1for i in range(n): v1 *= A[i]v2 = 1for j in range(m): v2 *= B[j]print(v1//v2)  곱셈을 덧셈으로 바꾸는 대표적인 방법이 로그를 취하는 것이다 $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}} = X$라고 하면 $$logX = log(a_{..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 7. 25.
• textsms

페리 수열(farey sequence) 조금 더 깊게2 - 페리 수열의 대칭성과 페리 수열의 합 -

1. 페리 수열의 대칭성(symmetry) n번째 페리 수열의 분수 $\frac{a}{b}$에 대해 생각해보자. 먼저 기약분수이므로 a,b가 서로소이고 0과 1 사이에 있으므로 a < b이다. https://deepdata.tistory.com/1104 페리 수열(farey sequence) 조금 더 깊게1 - 페리 수열의 길이 - 1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. deepdata.tistory.com 이전에 관찰했던 것처럼 n번째 페리 수열에는 분모가 n 이하인 정수 b에 대하여 b보다 작은 서로소인 모든 정수 a에 대해 $\..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms

[Java]분수를 소수점 20째자리까지 출력하는 방법

두 자연수 a,b를 입력받아 a/b를 소수점 20째자리까지 출력하라고 한다면 어떻게 해야할까? 일단 생각할 수 있는 방법은 %.20f 로 a/b를 출력하는 것이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int a=sc.nextInt(); int b=sc.nextInt(); System.out.printf("%.20f",(double)a/b); } } 근데 이렇게 하면 정답이 아니다 왜 이런 문제가 발생하냐면 자바에서 float 타입은 소수점 아래 9째자리까지 표현할 수 있고 double 타입은 18째자리까지만 표현할 수 있다...

• format_list_bulleted 정밀도
• · 2023. 2. 21.
• textsms