2016年06月02日 15:54

iljimae

edited: 2016年06月27日 20:55

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

Python 2.7.12 입니다.

import fractions as fr
print(fr.Fraction(int(b**0.5)-int(a**0.5),b-a))

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

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

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))

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);
}

#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;
}