Cod sursa(job #25299)
Utilizator | Data | 4 martie 2007 11:51:46 | |
---|---|---|---|
Problema | Puteri | Scor | 60 |
Compilator | cpp | Status | done |
Runda | preONI 2007, Runda 3, Clasa a 10-a | Marime | 2.02 kb |
#include<stdio.h>
#include<algorithm>
const int pr[40] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 10000};
const int maxn = 100001;
const int maxn2 = 128;
int a[maxn];
int j;
int solf;
int sol[maxn];
int n;
int i;
int b[maxn];
int c[maxn];
int mat[maxn2][maxn2][maxn2];
int prod;
int nr1;
void bkt(int i)
{
if (pr[i]<128 && prod < 128)
{
for(a[i] = 0; a[i] <= 1; ++a[i])
{
if (a[i] == 1)
{
nr1++;
prod *= pr[i];
}
bkt(i+1);
if (a[i] == 1)
{
nr1--;
prod /= pr[i];
}
}
}
else
{
if (prod < 128)
{
if (nr1 % 2 == 1) solf += sol[prod];
else solf -= sol[prod];
}
}
}
int main()
{
freopen("puteri.in","r",stdin);
freopen("puteri.out","w",stdout);
scanf("%d",&n);
prod = 1;
for(i = 1; i <= n; ++i)
{
scanf("%d %d %d", &a[i],&b[i],&c[i]);
}
for(i = 2; i <= 128; ++i)
{
for(j = 1; j <= n; ++j)
{
sol[i] += mat[(i-(a[j]%i))%i][(i-(b[j]%i))%i][(i-(c[j]%i))%i];
mat[a[j]%i][b[j]%i][c[j]%i]++;
}
for(j = 1; j <= n; ++j)
{
mat[a[j]%i][b[j]%i][c[j]%i]--;
}
}
memset(a,0,sizeof(a));
bkt(1);
printf("%d\n",solf);
return 0;
}