程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 5072 Coprime 同色三角形問題

HDU 5072 Coprime 同色三角形問題

編輯：C++入門知識

HDU 5072 Coprime 同色三角形問題

好吧，我承認就算當時再給我五個小時我也做不出來。

首先解釋同色三角形問題：

給出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 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<= 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;
}