Cod sursa(job #210863)

Utilizator albuaAlbu Alexandru albua Data 29 septembrie 2008 19:30:45
Problema Fractii Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <assert.h>
#define MAX 8000

FILE *f,*g;
long i,j,n,npedoi,temp,p,temp2;
char a[MAX][MAX];
int v[MAX];
long long contor;

int main()
{
  f=fopen("fractii.in","r");
  g=fopen("fractii.out","w");
  fscanf(f,"%ld\n",&n);
	contor=n*n-n+1;
  assert(n<MAX);
  npedoi=n/2;
  if(n%2==1)
    npedoi++;
  for(i=2;i<=npedoi;i++)
      {
	temp=0;
	for(j=2;i*j<=n;j++)
	  {
	    if(a[i][i*j]!=1)
	      {
		contor-=2;
		temp++;
		v[temp]=i*j;
		a[i][i*j]=1;
		a[i*j][i]=1;
	      }
	  }
	temp2=0;
	for(j=1;j<=temp;j++)
	  for(p=1;p<=temp;p++)
	    if(j!=p)
	    if(a[v[j]][v[p]]==0)
	      {
		temp2++;
		a[v[j]][v[p]]=1;
	      }
	  contor-=temp2;
      }
  fprintf(g,"%lld\n",contor);
  fclose(f);   fclose(g);
  return 0;
}