Submission | WnSOJ

Submission #39

ID	Time	User	Problem	Language	Verdict	Time	Memory
39	Apr/14/2025 12:54	admin	GCD Subset Challenge	cpp	AC	45 ms	6144 KB

Source Code

Theme:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
 
ll modexp(ll base, ll exp) {
    ll res = 1;
    while(exp) {
        if(exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> arr(n);
    int m = 0;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
        m = max(m, arr[i]);
    }
    vector<int> freq(m+1, 0);
    for(auto &x : arr) freq[x]++;
 
    vector<int> cnt(m+1, 0);
    for(int d = 1; d <= m; d++){
        for(int j = d; j <= m; j += d){
            cnt[d] += freq[j];
        }
    }
 
    vector<ll> f(m+1, 0);
    for(int d = 1; d <= m; d++){
        if(cnt[d]) f[d] = (modexp(2, cnt[d]) - 1 + MOD) % MOD;
    }
 
    vector<int> mu(m+1, 1), isComposite(m+1, 0), primes;
    for(int i = 2; i <= m; i++){
        if(!isComposite[i]){
            primes.push_back(i);
            mu[i] = -1;
        }
        for(auto p : primes){
            if(i * p > m) break;
            isComposite[i*p] = 1;
            if(i % p == 0){
                mu[i*p] = 0;
                break;
            } else {
                mu[i*p] = -mu[i];
            }
        }
    }
 
    ll ans = 0;
    for(int d = 1; d <= m; d++){
        ans = (ans + mu[d] * f[d]) % MOD;
    }
    if(ans < 0) ans += MOD;
    cout << ans;
    return 0;
}