HDU 3908 Triple (逆向思維)

題意：給定一個數組，判斷數組中這樣的三元組的個數：要麼三個元素兩兩互素，要麼三個元素兩兩都不互素。

ans=C(n,3) - 三個數中有一對互素的並且有一對不互素的個數sum

sum怎麼算？

對於num[i]，計算與之互素的元素的個數pnum，那麼不互素的元素的個數就是n-1-pnum了，對於num[i]而言，不滿足條件的三元組個數為pnum*(n-1-pnum)。

注意最後還要除2：比如(2, 3, 4)在處理2的時候算了一次，在處理4的時候也算了一次，但是在處理3的時候，肯定不會出現，因為對3而言，2與3互素，4也與3互素，所以總的來說每個三元組都多算了一次。

完整代碼：

/*1015ms,260KB*/

#include
const int maxn = 805;

int a[maxn];

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

int main()
{
	int t;
	scanf(%d, &t);
	while (t --)
	{
		int n;
		scanf(%d, &n);
		for (int i = 0; i < n; i++) scanf(%d, &a[i]);
		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			int num = 0;
			for (int j = 0; j < n; j++)
				if (i != j && gcd(a[i], a[j]) == 1) ++num;
			ans += num * (n - num - 1);
		}
		printf(%d
, n * (n - 1) * (n - 2) / 6 - ans / 2);
	}
	return 0;
}