Count number of sub-sequences with GCD 1 in C++: นับ subsequence ที่ GCD เท่ากับ 1

กำหนด array ของจำนวนเต็ม หาจำนวน subsequence (ลำดับย่อย) ที่มี GCD (ตัวหารร่วมมาก) เท่ากับ 1

ตัวอย่าง: arr = {3, 4, 8, 16} → Output: 7

Subsequences: (3,4), (3,8), (3,16), (4,3), (8,3), (16,3), (3,4,8)

หมายเหตุเกี่ยวกับโค้ดต้นฉบับ

โค้ดตัวอย่างใช้ nested loop ตรวจสอบ GCD ของคู่ (i,j) ซึ่งนับเฉพาะ subsequence ยาว 2 และนับซ้ำลำดับ (3,4) และ (4,3) แยกกัน วิธีนี้ไม่ใช่วิธีมาตรฐานในการนับ subsequence ทุกความยาว

วิธีแก้ปัญหาที่ถูกต้อง (Inclusion-Exclusion / DP)

วิธีที่ถูกต้องคือใช้ DP นับ subsequence ที่ GCD = d สำหรับทุก d แล้วคำนวณย้อนกลับ

ตัวอย่างโค้ด C++ (เวอร์ชันแก้ไข)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9+7;
int solve(vector<int> arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    vector<int> freq(maxVal+1);
    for(int x : arr) freq[x]++;
    
    vector<long long> dp(maxVal+1);
    for(int d = maxVal; d >= 1; d--) {
        long long cnt = 0;
        for(int m = d; m <= maxVal; m += d) cnt += freq[m];
        dp[d] = (cnt == 0) ? 0 : ((1LL << cnt) - 1); // 2^cnt - 1
        for(int m = 2*d; m <= maxVal; m += d)
            dp[d] = (dp[d] - dp[m] + MOD) % MOD;
    }
    return dp[1];
}

Input

{3, 4, 8, 16}