Language: C++

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
#define int64_t __int128_t


int main() {
	std::vector<int> fact_table(1000001);
	for (int i = 2; i <= 1000000; i++)
		if (!fact_table[i]) for (int j = 2; j <= 1000000 / i; j++) fact_table[i * j] = i;
	
	int n = ri();
	int a[n];
	for (int i = 0; i < n; i++) a[i] = ri();
	std::vector<int64_t> cnt(1000001);
	for (int i = 0; i < n; i++) cnt[a[i]] += a[i];
	
	std::vector<std::vector<int> > divs(1000001);
	divs[1] = {1};
	for (int i = 2; i <= 1000000; i++) {
		std::map<int, int> cur_yaku;
		int cur = i;
		while (fact_table[cur]) {
			cur_yaku[fact_table[cur]]++;
			cur /= fact_table[cur];
		}
		if (cur > 1) cur_yaku[cur]++;
		
		std::vector<int> cur_divs{1};
		for (auto &j : cur_yaku) {
			std::vector<int> next = cur_divs;
			int tmp = 1;
			for (int k = 1; k <= j.second; k++) {
				tmp *= j.first;
				for (auto l : cur_divs) next.push_back(l * tmp);
			}
			std::swap(next, cur_divs);
		}
		
		divs[i] = cur_divs;

/*
		if (i <= 50) {
			for (auto j : divs[i]) std::cerr << j << " ";
			std::cerr << std::endl;
		}*/
	}
	
	auto converted = cnt;
	for (int x = 1; x <= 1000000; x++) {
		for (int y : divs[x]) {
			if (y != x) converted[y] += converted[x];
		}
	}
	for (auto &i : converted) i *= i;
	for (int x = 1000000; x >= 1; x--) {
		for (int y : divs[x]) {
			if (y != x) converted[y] -= converted[x];
		}
	}
	for (int i = 0; i < n; i++) converted[a[i]] -= (int64_t) a[i] * a[i];
	int64_t ans = 0;
	for (int i = 1; i <= 1000000; i++) {
		ans += converted[i] / 2 / i;
		// if (converted[i]) std::cerr << i << ":" << converted[i] << std::endl;
	}
	std::cerr << ans << std::endl;
	
	
	return 0;
	
	std::map<int, int> yaku_[n];
	for (int i = 0; i < n; i++) {
		int cur = a[i];
		while (fact_table[cur]) {
			yaku_[i][fact_table[cur]]++;
			cur /= fact_table[cur];
		}
		if (cur > 1) yaku_[i][cur]++;
		
	}
	std::vector<std::pair<int, int> > yaku[n];
	for (int i = 0; i < n; i++) {
		for (auto &j : yaku_[i]) yaku[i].push_back(j);

	}
	
	int64_t sum[1000001];
	for (int i = 1; i <= 1000000; i++)
		for (int j = 1; j <= 1000000 / i; j++) sum[i] += cnt[i * j];
	
	int64_t s = std::accumulate(a, a + n, 0LL);
	
	
	int64_t res = 0;
	for (int i = 0; i < n; i++) {
		int size = yaku[i].size();
		int table[size];
		for (int j = 0; j < size; j++) {
			int tmp = 1;
			for (int k = 0; k < yaku[i][j].second; k++) {
				tmp *= yaku[i][j].first;
			}
			table[j] = tmp;
		}
		int64_t cur_sum = 0;
		int64_t gcd_i[1 << size];
		for (int j = 0; j < 1 << size; j++) {
			int64_t tmp_prod = 1;
			for (int k = 0; k < size; k++) {
				if (j >> k & 1) tmp_prod *= table[k] * yaku[i][k].first;
				else tmp_prod *= table[k];
			}
			int64_t cur_score = tmp_prod <= 1000000 ? sum[tmp_prod] : 0;
			gcd_i[j] = tmp_prod;
			
			for (int k = j; k = (k - 1) & j; ) {
				if ((__builtin_popcount(j ^ k) & 1)) gcd_i[j] -= gcd_i[k];
				else gcd_i[j] += gcd_i[k];
			}
		}
		for (int j = 0; j < 1 << size; j++) {
			for (int k = 0; k < size; k++) {
				
			}
		}
		std::cerr << cur_sum << std::endl;
		res += cur_sum * a[i];
		/*
		std::vector<int> yakus{1};
		for (auto &j : yaku[i]) {
			std::vector<int> next = yakus;
			int tmp = 1;
			for (int k = 1; k <= j.second; k++) {
				tmp *= j.first;
				for (auto l : yakus) next.push_back(l * tmp);
			}
			std::swap(next, yakus);
		}
		for (auto j : yakus) std::cerr << j << " ";
		std::cerr << std::endl;
		for (auto j : yakus) {
			
		}*/
		/*
		for (auto &j : yaku[i]) {
			// j.first * j.second
			int v = 1;
			for (int k = 0; k < j.second; k++) v *= j.first;
			int64_t prev = 0;
			for (int k = j.second; k; k--) {
				int64_t diff = sum[v] - prev;
				diff -= a[i];
				std::cerr << a[i] << " diff at " << j.first << "*" << k << "(" << v << ") : " << diff << " prev:" << prev << std::endl;
				cur -= (diff - diff / v) * a[i];
				prev = sum[v] - a[i];
				v /= j.first;
			}
		}*/
	}
	std::cout << res / 2  << std::endl;
	
	
	return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:71:19: error: ambiguous overload for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and '__int128')
   71 |         std::cerr << ans << std::endl;
      |         ~~~~~~~~~ ^~ ~~~
      |              |       |
      |              |       __int128
      |              std::ostream {aka std::basic_ostream<char>}
In file included from /usr/include/c++/14/istream:41,
                 from /usr/include/c++/14/sstream:40,
                 from /usr/include/c++/14/complex:45,
                 from /usr/include/c++/14/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:127,
                 from a.cc:1:
/usr/include/c++/14/ostream:174:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  174 |       operator<<(long __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:178:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  178 |       operator<<(unsigned long __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:182:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  182 |       operator<<(bool __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/14/ostream:1022:
/usr/include/c++/14/bits/ostream.tcc:96:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]'
   96 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/ostream:189:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  189 |       operator<<(unsigned short __n)
      |       ^~~~~~~~
/usr/include/c++/14/bits/ostream.tcc:110:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]'
  110 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/ostream:200:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  200 |       operator<<(unsigned int __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:211:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  211 |       operator<<(long long __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:215:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  215 |       operator<<(unsigned long long __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:231:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  231 |       operator<<(double __f)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:235:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(float) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  235 |       operator<<(float __f)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:243:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long double) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  243 |       operator<<(long double __f)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:573:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::operator<<(basic_ostream<_CharT, _Traits>&, char) [with _CharT = char; _Traits = char_traits<char>]'
  573 |     operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/14/ostream:579:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(basic_ostream<char, _Traits>&, char) [with _Traits = char_traits<char>]'
  579 |     operator<<(basic_ostream<char, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/14/ostream:590:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(basic_ostream<char, _Traits>&, signed char) [with _Traits = char_traits<char>]'
  590 |     operator<<(basic_ostream<char, _Traits>& __out, signed char __c)
      |     ^~~~~~~~
/usr/include/c++/14/ostream:595:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(basic_ostream<char, _Traits>&, unsigned char) [with _Traits = char_traits<char>]'
  595 |     operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c)
      |     ^~~~~~~~
a.cc:131:27: error: ambiguous overload for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and '__int128')
  131 |                 std::cerr << cur_sum << std::endl;
      |                 ~~~~~~~~~ ^~ ~~~~~~~
      |                      |       |
      |                      |       __int128
      |                      std::ostream {aka std::basic_ostream<char>}
/usr/include/c++/14/ostream:174:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  174 |       operator<<(long __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:178:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  178 |       operator<<(unsigned long __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:182:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  182 |       operator<<(bool __n)
      |       ^~~~~~~~
/usr/include/c++/14/bits/ostream.tcc:96:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]'
   96 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/ostream:189:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  189 |       operator<<(unsigned short __n)
      |       ^~~~~~~~
/usr/include/c++/14/bits/ostream.tcc:110:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]'
  110 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/ostream:200:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  200 |       operator<<(unsigned int __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:211:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  211 |       operator<<(long long __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:215:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  215 |       operator<<(unsigned long long __n)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:231:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  231 |       operator<<(double __f)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:235:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(float) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  235 |       operator<<(float __f)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:243:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long double) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]'
  243 |       operator<<(long double __f)
      |       ^~~~~~~~
/usr/include/c++/14/ostream:573:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::operator<<(basic_ostream<_CharT, _Traits>&, char) [with _