Cod sursa(job #493662)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 18 octombrie 2010 22:36:58
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#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();
}