Cod sursa(job #1455995)

Utilizator GilgodRobert B Gilgod Data 29 iunie 2015 17:01:22
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <iostream>
#include <fstream>
#include <bitset>

const char IN[] = "fractii.in", OUT[] = "fractii.out";
const int NMAX = 1000000;

using namespace std;

int N;
int parts[NMAX];

int gen() {
	int nr = N * 2 - 1;
	for (int i = 2; i <= N; ++i) {
		int part = parts[i] + N - i;
		int last = i + i;
		if (parts[i] == 0) {
			for (int j = i + i; j <= N; j += i)
				--part, last = j;
			for (int j = last, cnt = 0; j <= N && j > i; j -= i, ++cnt)
				parts[j] -= cnt;
		}	
		nr += part * 2;
	}
	return nr;
}

int main() 
{
	fscanf(fopen(IN, "r"), "%d", &N);
	fprintf(fopen(OUT, "w"), "%d\n", gen());
	return 0;
}