Cod sursa(job #2123601)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 6 februarie 2018 13:56:26
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

int64_t n;
unordered_map<int64_t, int64_t> m;

int64_t rec(int64_t x)
{
    if(m.find(x) != m.end())
        return m[x];
    int64_t ans = x*(x+1)/2;
    int64_t last = x/2, sq = sqrt(x);
    ans -= rec(x/2);
    ans -= (x+1)/2;
    for (int64_t i = 3; i <= sq; ++i){
        ans -= rec(x/i);
        ans -= (last-(x/i))*rec(i-1);
        last = x/i;
    }
    for (int64_t i = (x/sq); i > sq; --i)
        ans -= rec(x/i);
    m[x] = ans;
    return ans;
}

int main()
{
    ifstream fin ("fractii.in");
    ofstream fout ("fractii.out");
    fin >> n;
    m[1] = 1;
    m[2] = 2;
    m[3] = 4;
    fout << rec(n)*2-1 << "\n";
    fin.close();
    fout.close();
    return 0;
}