Pagini recente » Profil UPT_Patrascoiu_Teudan_Nume3 | Cod sursa (job #216021) | Cod sursa (job #1939439) | Cod sursa (job #2011847) | Cod sursa (job #357300)
Cod sursa(job #357300)
using namespace std;
#include<cstdio>
#define MAX_N 100002
int N;
int nr[MAX_N*10]; // nr[i] = nr de nr care se impart la i
int nrd[MAX_N*10], Max; // nrd[i] = nr de divizori primi a lui i
bool viz[MAX_N*10];
void eratostene()
{
int i,j;
for(i=2;i<=Max;i+=2) nrd[i]++;
for(i=3; i <= Max; i+=2)
{
if(nrd[i] == 0)
for(j=i; j<= Max; j+=i) ++nrd[j];
}
}
int main()
{
freopen("pairs.in","r",stdin);
freopen("pairs.out","w",stdout);
scanf("%d",&N);
long long sol = 0;
int i,j,a;
for(i=1;i<=N;++i)
{
scanf("%d",&a);
viz[a]=true;
if(a > Max) Max = a;
}
eratostene();
for(i = 2; i <= Max; ++i)
{
for(j=i;j<=Max;j+=i)
if(viz[j]) ++nr[i];
}
for(i=2;i<=Max;++i)
if(nrd[i]&1) sol += (long long)nr[i]*(nr[i]-1)/2;
else sol -= (long long)nr[i]*(nr[i]-1)/2;
printf("%lld\n",(long long)N*(N-1) - sol);
return 0;
}