Competitive-programming/Mobius Function.cpp at main · ArfatulAsif/Competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// Mobius inclusion exclusion

// Finding the number of co-primes pairs


const int N = 1e6+100;
int cnt[N];
bool sieve[N];
int mobius[N];
int D[N];
int arr[N];

void pre()
{
        memset(sieve, true, sizeof(sieve));

        for(int i=2;i<N;i++)
        {
                if(sieve[i])
                {
                        cnt[i] = 1;

                        for(int j=i+i;j<N;j += i)
                        {
                                sieve[j] = false;

                                if(cnt[j] == -1)
                                {
                                        continue;
                                }

                                cnt[j]++;

                                if(j % (i*i) ==0)
                                {
                                        cnt[j] = -1;
                                }
                        }
                }
        }

        mobius[1] = 1;
        mobius[2] = -1;

        for(int i=3;i<N;i++)
        {
                if(cnt[i]==-1)
                {
                        mobius[i] = 0;
                }
                else if(cnt[i]%2==0)
                {
                        mobius[i] = 1;
                }
                else
                {
                        mobius[i] = -1;
                }
        }


}


int32_t main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);

        int n;
        cin>>n;

        vector<int>v;
        for(int i=0;i<n;i++)
        {
                int a;
                cin>>a;
                v.push_back(a);
                arr[a]++;
        }

        pre();

        for(int d = N-50; d >= 1; d--)
        {
                int count = 0;
                for(int i = d; i<N; i += d)
                {
                        count += arr[i];
                }

                D[d] = count;
        }


        int ans = n*(n-1);
        ans /= 2;

        for(int i=2;i<N;i++)
        {
                ans += mobius[i]* (D[i]*(D[i]-1))/2; // Here mobius[i] works as a sign for inclusion exclusion.


        }

        cout<<ans<<endl;


}