Pagini recente » Cod sursa (job #2181481) | Cod sursa (job #1346510) | tema | Rating Petrila Cristian (petrila_cristian99) | Cod sursa (job #2123601)
#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;
}