Pagini recente » Cod sursa (job #1889786) | Cod sursa (job #2927678) | Cod sursa (job #2262585) | Cod sursa (job #2100598) | Cod sursa (job #1982406)
#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;
}