Cod sursa(job #2484639)

Utilizator razviii237Uzum Razvan razviii237 Data 31 octombrie 2019 12:00:15
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#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, long double x) {
    int p = 1 << 20, r = n+1, bad = 0;
    /*while(p > 0) {
        if(r - p > a && ((long 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 && ((long double)a / (r - p-1)) < x) { r -= p; }
        p >>= 1;
    }*/
    //cout << r << '\n';
    r = max(a+1, (int)ceil(a / x));
    if(r > n) { r = n + 1; }
    //cout << r << "\n\n";

    /*for(int i = n; i >= r; i --) {
        if(gcd(i, a) != 1) {
            bad ++;
        }
    }*/
    return n - r + 1 - bad;
}
xy findyfin(int a, long double x) {
    int p = 1 << 20, r = n+1;
    /*while(p > 0) {
        if(r - p > a && ((long 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 && ((long double)a / (r - p-1)) < x) { r -= p; }
        p >>= 1;
    }*/
    r = max(a+1, (int)ceil(a / x));
    if(r > n) { r = n + 1; }
    if(gcd(a, r) != 1) { ++ r; }
    return {a, r};
}

int tri(long 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(long 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 && (long double)y.x / y.y > (long double)ans.x / ans.y) {
            ans = y;
        }
    }
    g << ans.x << ' ' << ans.y << '\n';
}

int solve() {
    long 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;
}