Cod sursa(job #1982406)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 18 mai 2017 17:53:03
Problema Mins Scor 80
Compilator cpp Status done
Runda Simulare 12 Marime 1.02 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("mins.in"); ofstream fout ("mins.out");

const int nmax = 1e6;
const int mod = 666013;

vector<pair<long long, long long>> h[ mod ];

long long hfind (int x, int y) {
    int key = (1LL * x * nmax + y) % mod;
    for (const auto &i : h[ key ]) {
        if (i.first == 1LL * x * nmax + y) {
            return i.second;
        }
    }
    return -1;
}

void baga (int x, int y, long long k) {
    if (hfind(x, y) == -1) {
        h[(1LL * x * nmax + y) % mod].push_back( make_pair(1LL * x * nmax + y, k) );
    }
}

long long solve (int x, int y) {
    if (x == 0 || y == 0) return 0;

    if (x < y) swap(x, y);

    long long ans = hfind(x, y);
    if (ans != -1) return ans;

    ans = 1LL * x * y;

    for (int i = 2; i <= y; ++ i) {
        ans -= solve(x / i, y / i);
    }

    baga(x, y, ans);

    return ans;
}

int main() {
    int c, d;

    fin >> c >> d;
    -- c, -- d;

    fout << solve(c, d) << "\n";

    fin.close();
    fout.close();
    return 0;
}