코딩도장

변경이력

2 454개 문자 추가 2765개 문자 삭제

2016年06月27日 11:56

a,b의 범위가 굉장히 크기 때문에 전체 탐색으로 해결할 수 없습니다. 우선 어떠한 수가 홀수개의 약수만을 갖기위해선 그 수는 완전제곱수여야합니다. 그리고 [a,b]에서 a를 포함하지 않는 완전제곱수의 개수는 sqrt(b)-sqrt(a)입니다. 따라서 우리가 찾는 답은 c/d (c = sqrt(b)-sqrt(a), d = b-a) 입니다.이 분수를 기약분수로 만들기 위해서 분모와 분자를 분모와 분자의 최대공약수로 나누어주면 됩니다. 아래는 C++ 코드입니다. <div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"> ```{.cpp} #include <<iostream> > #include <<cstdlib> > #include <<cstdio> > #include <<cmath> > #include <<algorithm> using > 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; } </pre></div>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; } ```

1 Original

2016年06月02日 07:09

iljimae

a,b의 범위가 굉장히 크기 때문에 전체 탐색으로 해결할 수 없습니다. 우선 어떠한 수가 홀수개의 약수만을 갖기위해선 그 수는 완전제곱수여야합니다. 그리고 [a,b]에서 a를 포함하지 않는 완전제곱수의 개수는 sqrt(b)-sqrt(a)입니다. 따라서 우리가 찾는 답은 c/d (c = sqrt(b)-sqrt(a), d = b-a) 입니다.이 분수를 기약분수로 만들기 위해서 분모와 분자를 분모와 분자의 최대공약수로 나누어주면 됩니다. 아래는 C++ 코드입니다. <div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%">#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; } </pre></div>

코딩도장

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

피드백 · 개인정보취급방침 · RSS