HDU 5072 용 척 원리 + 질량 인수 분해

HDU 5072 제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=5072 제목: n 개 수 를 주 고 몇 개의 대수 (a, b, c) 가 있 는 지 물 어보 면 gcd (a, b) = gcd (b, c) = gcd (a, c) = 1 또는 gcd (a, b), gcd (b, c), gcd (a, c) 는 모두 1 이 아 닙 니 다.사고: 1 로 만 구 하 는 것 은 오히려 쉽다. 왜냐하면 숫자 는 모두 1e5 이내 에 하나의 질량 인수 분해 방식 으로 구 할 수 있 지만 두 번 째 조건 은 구하 기 어렵다.그래서 문 제 를 바 꾸 어 tans = 비합법적 인 대 수 를 구하 고 ans = 총수 - tans.몇 가지 예 를 들 어 모든 수 에 대해 그 와 서로 질 적 인 수의 수 u 를 구하 고 나머지 는 그 와 질 적 인 수 (n - 1 - u) 를 구하 지 않 으 면 tans = sigma (u * (n - 1 - u) / 2.증명 하면 대개 용 척 원리 로그런데 어떻게 그 와 서로 질 적 인 숫자 를 구 했 는 지.......................................................인터넷 에서 문제 풀이 보고 서 를 찾 는 것 이 냐, 아니면 용 척 원 리 를 이용 하여 구 하 는 것 이 냐?하나의 수 에 대해 질량 인 수 는 그 질량 인수 그룹 ele [] 를 분해 한 다음 에 모든 ele 는 최대 한 번 으로 구성 할 수 있 는 배 수 를 사용 하여 이 수의 계수 기 + 1 을 주 고 이 수 는 이러한 수 와 서로 질 이 없 음 을 나타 낸다.하나의 수의 상호 질 적 인 dp 를 구 할 때 같은 질량 인 수 를 분해 하여 질량 인수 배열 ele [] 를 얻 을 수 있 으 며, 각 ele 는 최대 한 번 으로 배수 temp 를 구성 합 니 다.만약 ele 가 홀수 개 를 사용 했다 면, dp + = num [temp] (num 은 계수기 이 고, temp 는 이 배 수 를 표시 합 니 다), 그렇지 않 으 면 dp - = num [temp].구체 적 으로 는 전 확률 공식의 원리 로 해석 할 수 있다.원본 코드:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define LL long long
const int MAXN = 200000 + 5;
int vis[MAXN];
int g[MAXN];
int num[MAXN];
int p[MAXN], cnt;
int data[MAXN];
void init()
{
    memset(vis, 0, sizeof(vis));
    cnt = 0;
    for(int i = 2 ; i < MAXN ; i++){
        if(vis[i] == 0){
            p[cnt++] = i;
            int u = i;
            while(u < MAXN) vis[u] = 1, u += i;
        }
    }
}
int ele[MAXN];
int main()
{
// freopen("C.in", "r", stdin);
    init();
    int t;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        memset(g, 0, sizeof(g));
        for(int i = 0 ; i < n ; i++)
            scanf("%d", &data[i]), g[data[i]] = 1;
        memset(num, 0, sizeof(num));
        for(int i = 0 ; i < n ; i++){
            cnt = 0;
            int temp = data[i];
            for(int j = 0 ; p[j] * p[j] <= temp ; j++){
                if(temp % p[j] == 0){
                    ele[cnt++] = p[j];
// printf("cnt = %d, p[j] = %d, temp = %d
", cnt, p[j], temp);
                    while(temp % p[j] == 0){
                        temp /= p[j];
// printf("temp = %d, p[j] = %d
", temp, p[j]);
                    }
                }
            }
            if(temp != 1)   ele[cnt++] = temp;
            for(int j = 0 ; j < (1 << cnt) ; j++){
                int which = 1;
                for(int k = 0 ; k < cnt ; k ++){
                    if((1 << k) & j)
                        which *= ele[k];
                }
                num[which]++;
            }
        }
// printf("second
");
        LL ans = 0;
        for(int i = 0 ; i < n ; i++){
            cnt = 0;
            int temp = data[i];
            for(int j = 0 ; p[j] * p[j] <= temp ; j++){
                if(temp % p[j] == 0){
                    ele[cnt++] = p[j];
                    while(temp % p[j] == 0) temp /= p[j];
                }
            }
            if(temp != 1)   ele[cnt++] = temp;
            LL tans = 0;
            for(int j = 1 ; j < (1 << cnt) ; j++){
                int sta = 0;
                LL which = 1;
                for(int k = 0 ; k < cnt ; k++){
                    if((1 << k) & j){
                        sta++,  which *= ele[k];
                    }
                }
                if(which > MAXN)    continue;
                if(sta & 1) tans += num[which];
                else    tans -= num[which];
            }
            if(tans > 0)    tans--;
            ans += tans * (n - 1 - tans);
        }
        ans = (LL)n * (n - 1) * (n - 2) / 6 - ans / 2;
        printf("%I64d
", ans);
    }
    return 0;
}