Pagini recente » Cod sursa (job #1611912) | Cod sursa (job #1376940) | Cod sursa (job #1421369) | Cod sursa (job #361618) | Cod sursa (job #2483049)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("farey.in");
ofstream g("farey.out");
int gcd(int x, int y) {
if(y == 0) {
return x;
}
return gcd(y, x % y);
}
struct xy { int x, y; };
int n, m, i, j, ans;
int findy(int a, double x) {
int p = 1 << 20, r = n+1, bad = 0;
/*while(p > 0) {
if(r - p > a && ((double)a / (r - p)) < x && gcd(a, r - p) == 1) {
r -= p;
} else if(r - p > a && r - p - 1 > a && gcd(a, r - p) != 1 && ((double)a / (r - p-1)) < x) { r -= p; }
p >>= 1;
}*/
r = max(a+1, (int)ceil(a / x));
for(int i = n; i >= r; i --) {
if(gcd(i, a) != 1) {
bad ++;
}
}
return n - r + 1 - bad;
}
xy findyfin(int a, double x) {
int p = 1 << 20, r = n+1;
while(p > 0) {
if(r - p > a && ((double)a / (r - p)) < x && gcd(a, r - p) == 1) {
r -= p;
}else if(r - p > a && r - p - 1 > a && gcd(a, r - p) != 1 && ((double)a / (r - p-1)) < x) { r -= p; }
p >>= 1;
}
return {a, r};
}
int tri(double x) {
int i, y, ans = 0;
for(i = 1; i <= n; i ++) {
y = findy(i, x);
ans += y;
}
return ans;
}
bool done = false;
void finale(double x) {
int i;
xy y;
xy ans = {0, 1};
for(i = 1; i <= n; i ++) {
y = findyfin(i, x);
if(y.y != n + 1 && (double)y.x / y.y > (double)ans.x / ans.y) {
ans = y;
}
}
g << ans.x << ' ' << ans.y << '\n';
}
int solve() {
double st, dr, mid;
st = 0; dr = 1;
while(done == false) {
mid = (st + dr)/2;
int hm = tri(mid);
if(hm == m) {
done = true;
finale(mid);
} else
if(hm > m) {
dr = mid;
} else {
st = mid;
}
}
}
int main()
{
f >> n >> m;
solve();
f.close(); g.close();
return 0;
}