상품 is 뭔들 (2016 인하대 프로그래밍 경진대회 B번)

출처: https://www.acmicpc.net/problem/12779

정보통신처에서는 2016년 6월 4일 인하 광장에서 이벤트를 진행하려고 한다. 정보통신처에서 인하 광장에 올린 게시글에 N번째로 댓글을 단 모든 학생에게 상품을 지급하기로 하였다. 단, N은 약수의 개수가 홀수여야 한다. 인하 광장을 즐겨보는 찬미는 이 이벤트에 참가하기로 하였다. 찬미는 댓글을 작성한 후 자신이 상품을 받을 확률이 얼마나 되는지 궁금해졌다. 찬미가 댓글을 작성하기 전의 총 댓글 수가 a개이고, 댓글을 작성 후의 총 댓글 수가 b개일 때 찬미의 댓글은 a보다 크고 b보다 작거나 같은 범위 안에 존재한다고 한다. 예를 들어 a가 1이고, b가 4인 경우 [2, 3, 4] 중 한 곳에 댓글이 존재한다. 이 중 약수의 개수가 홀수인 숫자는 4, 한 개이므로 상품을 받을 확률은 1/3이다. 찬미를 도와 찬미가 상품을 받을 확률을 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 정수 a와 b가 주어진다. (1 ≤ a, b ≤ 2^60) b는 a보다 항상 크다

출력

찬미가 상품을 지급받을 확률을 기약분수 형태로 출력한다. 만약 확률이 0인 경우 0을 출력한다.

예제 입력

1 4

예제 출력

1/3
수학 유클리드 호제법
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

14개의 풀이가 있습니다. 1 / 2 Page

a,b의 범위가 굉장히 크기 때문에 전체 탐색으로 해결할 수 없습니다. 우선 어떠한 수가 홀수개의 약수만을 갖기위해선 그 수는 완전제곱수여야합니다. 그리고 [a,b]에서 a를 포함하지 않는 완전제곱수의 개수는 sqrt(b)-sqrt(a)입니다. 따라서 우리가 찾는 답은 c/d (c = sqrt(b)-sqrt(a), d = b-a) 입니다.이 분수를 기약분수로 만들기 위해서 분모와 분자를 분모와 분자의 최대공약수로 나누어주면 됩니다. 아래는 C++ 코드입니다.

#include <iostream> 
#include <cstdlib> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
using namespace std;

typedef long long ll;  

ll gcd(ll a,ll b){
    if (b == 0) return a; 
    return gcd(b,a%b); 
}

int main(){
    ll a,b; 
    cin >> a >> b;  
    ll d = b-a;  
    ll c = int(sqrt(b))-int(sqrt(a)); // 범위안에 약수의 개수가 홀수인 수의 개수 
    if (c == 0) cout << 0 << endl; 
    else{
        ll g = gcd(c,d); // 기약분수로 만드는 과정 
        cout << (c/g) << "/" << (d/g) << endl; 
    }
    return 0; 
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
while __name__ == '__main__':
    print((lambda a, b: __import__('fractions').Fraction(int(b**0.5) - int(a**0.5),b-a))(*list(map(int, input('a, b:').split()))))

파이썬 3.5.1 64

이렇게 한줄로 코드 작성하는 방법은 어떻게 공부해야 하나요? 매우 세련되어 보입니다. 보면 대충 이해는 가는데 문법을 잘 모르겠습니다. - Dr.Choi, 2016/07/03 23:07 M D
문법 자체는 어렵지 않습니다. 기껏해야 lambda 응용입니다. 그냥 길게 작성한 뒤에 줄이려고 노력해 보세요. 다만 연습이니까 이리 줄여도 되는 거지, 가독성을 위한다면 적절히 줄이는 것이 좋습니다. - Flair Sizz, 2016/07/03 23:22 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬 2.7입니다. 뭔가 잘못된거 같기도 한데..

a, b = 1, 4
print("%d/%d" %(int(b ** 0.5) - int (a ** 0.5), b - a))

기약분수로 만들어주세요. - Flair Sizz, 2016/06/26 16:53 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Java로 구현하였습니다.

import java.util.Scanner;

public class GiftIsWhat {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine();
        String[] parsedData = str.split(" ");

        int a = Integer.parseInt(parsedData[0]);
        int b = Integer.parseInt(parsedData[1]);

        int temp1 = 0;

        for (int i = a + 1; i <= b; i++) {
            int temp2 = (int)Math.sqrt(i);
            if (i == temp2 * temp2)
                temp1++;
        }

        if (temp1 == 0)
            System.out.println("0");
        else {
            int temp4 = gcd (b - a, temp1);
            temp1 = temp1 / temp4;
            int temp3 = (b - a) / temp4;
            System.out.println(String.valueOf(temp1) + "/" + String.valueOf(temp3));
        }
    }

    public static int gcd(int p, int q) {
        if (q == 0) return p;
        return gcd(q, p % q);
    }
}

gcd() 함수 참고 : https://ko.wikipedia.org/wiki/유클리드_호제법

좀 느려터진 방법 같기도 합니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

루비 내장함수 Rational.

odds = ->a,b { Rational((b**0.5).to_i-(a**0.5).to_i, b-a) }

Test

expect(odds[1, 4]).to eq "1/3".to_r
expect(odds[1,16]).to eq "1/5".to_r
expect(odds[1,2**60]).to eq "1/1073741825".to_r

Output

#=> puts odds[1,16]  3/15 => Rational에 의해 1/5 출력됨.
1/5
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
in.fun = function(a, b){
  tmp = c((a+1):b)
  step = lapply(tmp, function(x) seq_len(x)[x%%seq_len(x) == 0] %>% length) %>% unlist
  return(paste0(tmp[which(step%%2 != 0)] %>% length, "/", length(tmp)) )

}

> in.fun(a = 1, b= 4)
[1] "1/3"

R

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def yaksu(a):
    c=[]
    d=int(pow(a,2))
    for i in range(1,d+1):
        if a % i == 0 :
            c.append(i)
    return len(c)
def maxyak(a,b):
    n=a%b
    if n == 0:
        return b
    else:
        return maxyak(b,n)
ans=0
a,b=input().split()
for i in range(int(a)+1,int(b)+1):
    if yaksu(i) % 2 == 1:
        ans+=1
l=int(b)-int(a)
if ans == 0 :
    print("0")
else:
    k=maxyak(ans,int(b)-int(a))
    print(int(ans/k),"/",int(l/k))

어마어마한 시간이 걸리는 군요. 수학 공부를 해야겠어요. - Dr.Choi, 2016/07/03 22:42 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

c언어입니다!. 분모를 b-a로 두고, 분자를 반복문을돌려 N^2 > a 이면서, N^2 <= b 인 N값을 카운트하였습니다. 그리고 약분은 유클리드호제법으로 최대공약수를구한후 기약분수로 만들었습니다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>

int Euclid(int a, int b)
{
    if (a == 0 || b == 0)
        return 1;
    int max, min;

    if (a < b)
    {
        min = a;
        max = b;
    }
    else
    {
        max = a;
        min = b;
    }
    int value = max % min;
    while (value)
    {
        max = min;
        min = value;
        value = max % min;
    }
    return min;
}
int main()
{
    long long a = 0, b = 0;
    scanf(" %lld", &a);
    scanf(" %lld", &b);//a<b
    long long N = 2;
    int count = 0;
    while (N*N <= a)
    {
        N++;
    }

    while (N*N <= b)
    {
        count++;
        N++;    
    }

    long long all = b - a;
    int gCD = Euclid(all, count);
    if (count == 0)
        printf("0");
    else
        printf("%d/%lld", count / gCD, all /gCD);
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python 2.7.12 입니다.

import fractions as fr
print(fr.Fraction(int(b**0.5)-int(a**0.5),b-a))
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include <stdio.h>
#include <stdlib.h>
int getNdivisor(int value);
void main(void) {

    int a = 1;
    int b = 4;

    int out_bottom = b -a;
    int out_up = 0;

    for(int i = a+1 ; i <=b ; i++) {
        if(getNdivisor(i)%2 !=0) {
            out_up++;
        }
    }

    printf("\n%d / %d\n", out_up, out_bottom);

}

int getNdivisor(int value) {
    int count = 0;

    for(int i = 1 ; i <= value; i++) {
        if(value%i == 0)
            count++;
    }

    return count;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

수학 x 4
유클리드 호제법 x 1
연관 문제

언어별 풀이 현황
전 체 x 14
cpp x 2
python x 5
기 타 x 3
ruby x 1
r x 1
java x 2