Cod sursa(job #109693)

Utilizator mastermageSchneider Stefan mastermage Data 25 noiembrie 2007 12:26:20
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <math.h>
#include <set>
using namespace std;

#define maxN 100100
#define maxM 1000100

typedef long long lint;

int n,v[maxN],p,prm[maxN];
lint res;
int erat[maxM];

set<int> mul[maxN];

void inputFunc(){FILE*fi=fopen("pairs.in","r");fscanf(fi,"%d",&n);for(int i=0;i<n;i++){int c;fscanf(fi,"%d",&c);v[i]=c;}fclose(fi);}
void outputFunc(){FILE*fi=fopen("pairs.out","w");fprintf(fi,"%lld",res);fclose(fi);}
void era(int n){
	int i,t=sqrt((double)n);
	for(i=2;i<=t;i++)if(!erat[i]){
		erat[i]=p;
		prm[p++]=i;
		for(int j=i+i;j<=n;j+=i)erat[j]=1;
	}
	for(;i<=n;i++)if(!erat[i])erat[i]=p,prm[p++]=i;
}

int main(){
	return 0;
	inputFunc();
	
	era(1000000);
	
	for(int i=0;i<n;i++){
		int c=v[i],t=sqrt((double)c);
		set<int> x;
		for(int j=0;prm[j]<=t;j++){
			int d=prm[j];
			if(c%d==0){	
				x.insert(mul[j].begin(),mul[j].end());
			
				mul[j].insert(i);
				
				
				do{c/=d;}while(c%d==0);
			}
		}
		if(c!=1){
			int j=erat[c];
			x.insert(mul[j].begin(),mul[j].end());
		
			mul[j].insert(i);
		}
		
		res+=i-x.size();
		
	}
	
	outputFunc();
	return 0;
}