Pagini recente » Cod sursa (job #435173) | Cod sursa (job #2396410) | Cod sursa (job #1220338) | Cod sursa (job #1916499) | Cod sursa (job #493662)
Cod sursa(job #493662)
#include<iostream>
#include<cstring>
#include<fstream>
using namespace std;
int main()
{
int n,count[1000001],mark[1000001],curent[1000001];
ifstream in("fractii.in");
ofstream out("fractii.out");
in>>n;
count[1]=n;
for(int i=2;i<=n;i++)
count[i]=1;
memset(mark,0,sizeof(mark));
for(int i=2;i<=n;i++)
{
int marked=0,j;
if(mark[i]==1)
marked++;
memset(curent,0,sizeof(curent));
curent[i]=1;
for(j=i+i;j<=n;j+=i)
{
curent[j]+=curent[j-i];
count[j]+=curent[j];
if(mark[j]==1)
{
count[j]-=marked;
marked++;
}
}
curent[i]=0;
j-=i;
if(mark[j]==1)
marked=1;
else
marked=0;
memset(curent,0,sizeof(curent));
curent[j]=1;
j-=i;
for(;j>=0;j-=i)
{
curent[j]+=curent[j+i];
count[j]+=curent[j];
if(mark[j]==1)
{
count[j]-=marked;
marked++;
}
}
for(j=i+i;j<=n;j+=i)
mark[j]=1;
mark[i]=1;
}
int sum=0;
sum+=count[1];
for(int i=2;i<=n;i++)
sum+=count[i];
out<<sum<<endl;
in.close();
out.close();
}