程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu5072 Coprime 2014鞍山現場賽C題計數+容斥

hdu5072 Coprime 2014鞍山現場賽C題計數+容斥

編輯：C++入門知識

hdu5072 Coprime 2014鞍山現場賽C題計數+容斥

Coprime

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 354 Accepted Submission(s): 154

Problem Description There are n people standing in a line. Each of them has a unique id number.

Now the Ragnarok is coming. We should choose 3 people to defend the evil. As a group, the 3 people should be able to communicate. They are able to communicate if and only if their id numbers are pairwise coprime or pairwise not coprime. In other words, if their id numbers are a, b, c, then they can communicate if and only if [(a, b) = (b, c) = (a, c) = 1] or [(a, b) ≠ 1 and (a, c) ≠ 1 and (b, c) ≠ 1], where (x, y) denotes the greatest common divisor of x and y.

We want to know how many 3-people-groups can be chosen from the n people.
Input The first line contains an integer T (T ≤ 5), denoting the number of the test cases.

For each test case, the first line contains an integer n(3 ≤ n ≤ 10⁵), denoting the number of people. The next line contains n distinct integers a₁, a₂, . . . , a_n(1 ≤ a_i ≤ 10⁵) separated by a single space, where a_i stands for the id number of the i-th person.
Output For each test case, output the answer in a line.
Sample Input

1
5
1 3 9 10 2

Sample Output

Source 2014 Asia AnShan Regional Contest
題意：給n個數，問三個數兩兩互質或者兩兩不互質的三元組有多少種。。分析：當時做重現的真心不會233，今天翻大白發現竟然有這個模型233。(p105 問題6) 就是經典的單色三角形模型，從反面考慮，求出所以非單色三角形即可。對於每一個數，求與其互質和不互質的個數是多少個，記與其互質的是ai個，那麼包括第i個數的就有ai*(n-1-ai)種，最後求和，注意到每個非單色三角形出現了兩次，所以還要除2.最後用總的情況C(n,3)減去就好。現在的問題是如何求與每個數互質的個數。求1到k與x互質的數的個數用容斥搞，詳見poj1142. 那麼這道題求n個數與x互質的數個數也用容斥。由於數的范圍不大，只有10^5,所以我們可以預處理出1到10^5每個數作為是這n個數中多少個數的因子。然後求出x的質因子，然後再容斥計算就好。。。。唉。。還是見識短淺做題少。

/**
 * @author neko01
 */
//#pragma comment(linker, /STACK:102400000,102400000)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;
typedef long long LL;
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define clr(a) memset(a,0,sizeof a)
#define clr1(a) memset(a,-1,sizeof a)
#define dbg(a) printf(%d
,a)
typedef pair pp;
const double eps=1e-9;
const double pi=acos(-1.0);
const int INF=0x7fffffff;
const LL inf=(((LL)1)<<61)+5;
const int N=100005;
const int M=500;
bool isprime[M];
int prime[M];
int tot=0,n;
int fac[50];
bool have[N];
int a[N];
int s[N];  //sum[i]表示a[i]中能整除i的個數
void getprime()
{
    for(int i=2;i<=M;i++)
    {
        if(isprime[i]) continue;
        prime[tot++]=i;
        for(int j=i*i;j<=M;j+=i)
            isprime[i]=true;
    }
}
LL gao()
{
    LL ans=0;
    for(int i=0;i