출처: 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
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;
}
2016年06月02日 16:09
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);
}
2016年07月04日 00:33
풀이 작성
코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.