Pagini recente » Cod sursa (job #887351) | Cod sursa (job #2123599)
#include <bits/stdc++.h>
using namespace std;
int n;
unordered_map<int, int> m;
int rec(int x)
{
if(m.find(x) != m.end())
return m[x];
int ans = x*(x+1)/2;
int last = x/2, sq = sqrt(x);
ans -= rec(x/2);
ans -= (x+1)/2;
for (int i = 3; i <= sq; ++i){
ans -= rec(x/i);
ans -= (last-(x/i))*rec(i-1);
last = x/i;
}
for (int 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;
}