Okay, I admit I couldn’t have done it in five more hours.
First, explain the same color triangle problem:
Given n(n >= 3) points, some of these points are colored red and the rest are colored black. And then you connect these points two by two, so that every three points form a triangle,
So there are a total of triangles that sum is equal to C(3,n). A triangle is a homochromatic triangle if all three points are of the same color.
So a very intuitive idea is to contain and exclude sum – the number of different triangles ans.
ans = (sigma (Xi*Yi) ) / 2; (1 <= I <= n,Xi,Yi represent the number of red and black points connected with the ith point respectively.)
When it’s bad, the code looks like shit.
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #pragma comment(linker, "/STACK:1024000000") #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f using namespace std; int divi[100010][130]; bool is[100010]; int num[100010]; int mem[100010]; int ch[1001]; int Check(int x) { int ans = 0; while(x) ans += (x&1),x >>= 1; return ans&1 ? 1:1; } int main() { int n = 100000,i,j,k; for(i = 0; i <= 1000; ++i) ch[i] = Check(i); for(i = 1; i <= n; ++i) divi[i][0] = 0; memset(is,false,sizeof(is)); for(i = 2; i <= n; ++i) { if(is[i] == false) { divi[i][++divi[i][0]] = i; for(j = i+i; j <= n; j += i) { divi[j][++divi[j][0]] = i; is[j] = true; } } } int Max,Mul,t; int wf; for(i = 1; i <= n; ++i) { Max = (1<<divi[i][0]) - 1; wf = divi[i][0]; for(j = 1; j <= Max; ++j) { for(Mul = 1,t = 1,k = wf; k >= 1; --k,t <<= 1) { if((j&t) && j ! = t) Mul *= divi[i][k]; } if(Mul ! = 1) divi[i][++divi[i][0]] = Mul*ch[j]; } } int T,tmp; LL ans,sum; int Top; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(is,false,sizeof(is)); for(i = 1,Top = 0; i <= n; ++i) { scanf("%d",&num[i]); is[num[i]] = true; Top = max(Top,num[i]); } ans = 0; memset(mem,-1,sizeof(mem)); LL anw = 0; for(i = 1; i <= n; ++i) { tmp = num[i]; ans = 0; for(j = divi[tmp][0]; j >= 1; --j) { if(mem[abs(divi[tmp][j])] ! = -1) sum = mem[abs(divi[tmp][j])]*(divi[tmp][j]/abs(divi[tmp][j])); else { sum = 0; for(k = abs(divi[tmp][j]); k <= Top; k += abs(divi[tmp][j])) sum += is[k] ? 1:0; mem[abs(divi[tmp][j])] = sum; sum *= (divi[tmp][j]/abs(divi[tmp][j])); } ans += sum; } if(ans) anw += (n-ans)*(ans-1); } LL tn = n; printf("%I64d\n",tn*(tn-1)*(tn-2)/6 -anw/2); } return 0; }Copy the code