Tekijät

input/code.cpp: In function 'int main()':
input/code.cpp:37:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k=0; k<v.size(); ++k){
                           ~^~~~~~~~~

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

typedef long long ll;

ll t[1111000], jakajia[1111000], r[1111000], pot2[11];


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //Älä käytä, jos tehtävä on interaktiivinen!
    for (int i=2; i<=1000000; ++i){
        if (t[i]==0){
            jakajia[i]=1;
            for (int j=i*2; j<=1000000; j+=i) {
                t[j]=i;
                jakajia[j]++;
            }
        }
    }
    pot2[1]=2;
    for (int i=2; i<=10; ++i) pot2[i]=pot2[i-1]*2;
    ll n;
    cin >> n;
    ll a;
    for (int i=1; i<=n; ++i){
        cin >> a;
        vector<int> v;
        while (t[a]){
            if (v.size()==0 || v[v.size()-1]!=t[a]) v.push_back(t[a]);
            a = a/t[a];
        }
        if (a>1 && (v.size()==0 || v[v.size()-1]!=a)) v.push_back(a);
        for (int j=1; j<pot2[v.size()]; ++j){
            int b=1;
            for (int k=0; k<v.size(); ++k){
                if (j&(1<<k)){
                    b*=v[k];
                }
            }
            r[b]++;
        }
    }
    ll yhttek=0;
    for (int i=2; i<=1000000; ++i){
        if (jakajia[i]%2==1) yhttek+=r[i]*(r[i]-1)/2;
        else yhttek-=r[i]*(r[i]-1)/2;
    }
    cout << n*(n-1)/2-yhttek << "\n";
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 2, 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED

Test 6

Group: 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED