Cod sursa(job #774724)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 6 august 2012 14:20:30
Problema Pairs Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
#include<string.h>
#define dim 1000005
using namespace std;

ifstream f("pairs.in");
ofstream g("pairs.out");

long long  p[dim],X[dim];


int main (){
	long long   x,n,i,j,MAX;
	long long res=0;
	f>>n;
	MAX=0;
	for(i=1;i<=n;i++){
		f>>x;
		p[x]=1;
		if(MAX<x)
			MAX=x;
	}long long w=0;
	w=(long long)(n*(n-1))/2;
	for(i=2;i<=MAX;++i){
		
		for(j=i;j<=MAX;j+=i){
			
			X[i]+=p[j];
			
		}
	}
	memset(p,0,sizeof(p));
	for(i=2;i<=MAX;++i) {
		if(p[i]==0){
			
			for(j=i;j<=MAX;j+=i)
				if(p[j]>=0)
					p[j]++;
			for(j=(long long)i*i;j<=MAX;j+=(long long )i*i)
				p[j]=-1;
		}
	}
		
	for(i=2;i<=MAX;++i){
		
		if(p[i]>0){
			
			if(p[i]%2)
				res+=(long long)((long long )(X[i])*(X[i]-1))/2;
			else
				res-=(long long)((long long )(X[i])*(X[i]-1))/2;
			
		}
		
	}
	g<<w-res<<"\n";
	return 0;
}