나도 짜옴

include<stdio.h>

#define INT_MAX (1LL<<63)-1

long long int gcd(long long int a, long long int b){

    if(a<b) return gcd(b,a);

    if(b==0) return a;

    return gcd(b,a%b);

}

main(){

    long long int i,j;

    for(i=10;i<INT_MAX;i++){

        for(j=i/10;j<i*10;j++){

            if(i==j)continue;

            long long int a = i/10;

            long long int b = i%10;

            long long int c = j;

            long long int d = 1;

            while(c>=10){

                c /= 10;

                d *= 10;

            }

            d = j%d;

            

            if(i==b*gcd(i,j)&&j==c*gcd(i,j)&&a==d){

                printf("%lld/%lld\n",i,j);

            }

            if(i==a*gcd(i,j)&&j==d*gcd(i,j)&&b==c){

                printf("%lld/%lld\n",i,j);

            }

        }

    }

}


일단 베이직하게 C문법이고, 문자열갖고 돌리는게 아니고 정수 자체로 약분하는 로직임.

부르트 포스라서 탐색 시간이 엄청 길긴 한데 분자 분모 크기순서대로 출력되는 장점은 있음


밑에 누가 코드 올려준거들이랑은 로직이 다름. 정수 파싱하는데 생각안나서 고민 좀 하긴 했는데 자릿수 구하는 부분만 손보면 생각보다 충분히 시간 줄어들듯?


시간 복잡도는 O(IJlnJ)정도 되는거같음. 자릿수 구하는거 잘 손보면 아마 O(IJ)정도?


실제 구한 값은

16/64

19/95

26/65

64/16

65/26

95/19

424/742

545/654

664/166

665/266

847/484

995/199

3243/4324

6664/1666

6665/2666

9995/1999

까지 구하는데도 오래 걸리긴 함