HDU 5072 Coprime 同色三角形问题

jiyuzi

好吧，我承认就算当时再给我五个小时我也做不出来。

首先解释同色三角形问题：

给出n(n >= 3)个点，这些点中的一些被涂上了红色，剩下的被涂上了黑色。然后将这些点两两相连，于是每三个点都会组成一个三角形，

即总共有sum = C(3,n)个三角形。对于一个三角形，如果三个点颜色一样则称其为同色三角形。

那么一个很直观的思路就是容斥，sum - 非同色三角形个数ans。

ans = (sigma (Xi*Yi) ) / 2;(1 <= i <= n,Xi,Yi分别表示与第 i 个点相连的红色点和黑色点的个数。)

状态不好的时候，代码写的就像屎一样。

#include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000")#define EPS (1e-8)#define LL long long#define ULL unsigned long long#define INF 0x3f3f3f3fusing 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 = Check(i);    for(i = 1;i <= n; ++i)        divi[0] = 0;    memset(is,false,sizeof(is));    for(i = 2;i <= n; ++i)    {        if(is == false)        {            divi[++divi[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[0]) -="" 1;="" wf="divi[0];" for(j="1;j" = 1; --k,t <<= 1)            {                if((j&t) && j != t)                    Mul *= divi[k];            }            if(Mul != 1)                divi[++divi[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);            is[num] = true;            Top = max(Top,num);        }        ans = 0;        memset(mem,-1,sizeof(mem));        LL anw = 0;        for(i = 1;i <= n; ++i)        {            tmp = num;            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;