Tekijät

input/code.cpp: In function 'std::vector<int> primes(int)':
input/code.cpp:46:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (n > 2)
     ^~
input/code.cpp:48:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     return ans;
     ^~~~~~
input/code.cpp: In function 'std::vector<int> uprimes(int)':
input/code.cpp:69:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (n > 2)
     ^~
input/code.cpp:71:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     return ans;
     ^~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:121:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nums.size(); i++) {
                  ~~^~~~~~~~~~~~~
input/code.cpp:124:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; pi <...

#pragma GCC optimize ("O3")

#include <stdio.h> // include before iostream for faster scanf
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <set>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <queue>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <tuple>
#include <utility>
#include <iomanip>
#include <iterator>
#include <bitset>

using namespace std;
typedef long long LL;

#define printv(printVec) for (auto printVecIter : (printVec)) cout << printVecIter << " "; cout << endl;

// g++ -Wall -Wshadow -std=c++11 a.cpp && ./a.out


vector<int> primes(int n) {
	vector<int> ans;
    while (n % 2 == 0) {
        ans.push_back(2);
        n = n/2;  
    }
    for (int i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0)  
        {
        	ans.push_back(i);
            n = n/i;  
        }  
    }
    if (n > 2)
    	ans.push_back(n);
   	return ans;
}



vector<int> uprimes(int n) {
	vector<int> ans;
    while (n % 2 == 0) {
    	if ((ans.size() && ans.back() != 2) || ans.size() == 0)
        	ans.push_back(2);
        n = n/2;  
    }
    for (int i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0)  
        {
        	if ((ans.size() && ans.back() != i) || ans.size() == 0)
        		ans.push_back(i);
        	// ans.push_back(i);
            n = n/i;  
        }  
    }
    if (n > 2)
    	ans.push_back(n);
   	return ans;
}


bool isprime(int n) {
	vector<int> ans;
    for (int i = 2; i <= sqrt(n); i = i + 2) {
        if (n % i == 0)  
        {
        	return false;
        }  
    }
    return true;
}

int PLIM = 1000;

int main() {
	std::ios::sync_with_stdio(false);cin.tie(0);
	int n; cin>>n;
	int maxnum = 0;
	vector<int> nums;
	vector<int> numcnt(1000001);
	vector<int> numidx(1000001, -1);
	map<int,vector<int>> m;
	LL ans = 0;
	LL ones = 0;
	for (int i =0;i<n; i++) {
		int nn; cin>>nn;
		if (nn == 1) {
			ones++;
			continue;
		}
		maxnum = max(nn, maxnum);
		numidx[nn] = nums.size();
		nums.push_back(nn);
	}
	sort(nums.begin(), nums.end());
	ans += ones * nums.size() + ones*(ones-1)/2;
	
	vector<int> primes_under_lim;
	vector<int> prime_to_idx(PLIM + 1);
	for (int i = 2; i <= PLIM; i++) {
		if (isprime(i)) {
			prime_to_idx[i] = primes_under_lim.size();
			primes_under_lim.push_back(i);
		}
	}
	vector<bitset<100000>> bitsets(primes_under_lim.size());
	bitset<100000> tmp;
	for (int i = 0; i < nums.size(); i++) {
		auto asd = uprimes(nums[i]);
		int pi = 0;
		for (; pi < asd.size() && asd[pi] < PLIM; pi++) {
			int idx = prime_to_idx[asd[pi]];
			tmp |= bitsets[idx];
			bitsets[idx].set(i);
		}
		int out = tmp.count();
		for (; pi < asd.size(); pi++) {
			int zxc = nums[i] - asd[pi];
			// cout << nums[i] << "  " << asd[pi] << endl;
			while (zxc > 0) {
				if (numcnt[zxc] && !tmp[numidx[zxc]]) {
					out += numcnt[zxc];
				}
				zxc -= asd[pi];
			}
		}
		numcnt[nums[i]]++;
		int add = i-out;
		ans += add;
		tmp.reset();
	}
	cout << ans << endl;
}

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: TIME LIMIT EXCEEDED

Test 5

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED