Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problem: H. Coprime Ribs
- // Contest: Codeforces - UTPC Contest 03-05-21 Div. 2 (Beginner)
- // Memory Limit: 256 MB
- // Time Limit: 1000 ms
- // Date / Time: 2021-09-27 13:49:56
- // Author: cosenza
- // всё что ни делается - всё к лучшему
- // check list -> long long, special cases, array size, mod (a*b%p*c%p not a*b*c%p , (a-b+p)%p not a-b )
- //
- // Powered by CP Editor (https://cpeditor.org)
- //#pragma GCC optimize("Ofast")
- //#pragma GCC optimize ("unroll-loops")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- //THESE ARE LAST DITCH EFFORTS!!!
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1e6 + 7;
- long long comp[maxn];
- vector<long long> primes;
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int n;
- cin >> n;
- for(long long i=2ll;i<maxn;i++){
- if(comp[i]) continue;
- for(long long j=i*i;j<maxn;j+=i) comp[j]=1;
- }
- for(long long i=2ll;i<maxn;i++){
- if(!comp[i]) primes.push_back(i);
- }
- vector<int> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- }
- vector<set<int>> pfs(n);
- for(int i = 0; i < n; i++) {
- int k = v[i];
- while(k % 2 == 0) {
- k /= 2;
- pfs[i].insert(2);
- }
- for(int j = 3, kk = 2; j * j <= k; j = primes[kk], kk++) {
- while(k % j == 0) {
- k /= j;
- pfs[i].insert(j);
- }
- }
- if(k > 2) {
- pfs[i].insert(k);
- }
- }
- map<int, int> cnt, sgn;
- for(int i = 0; i < n; i++) {
- int q = 1;
- for(auto k : pfs[i]) {
- q *= k;
- }
- cnt[q]++;
- sgn[q] = pfs[i].size();
- }
- int ansi = 0;
- for(auto itr : sgn) {
- int x = itr.second, y = cnt[itr.first];
- int tor = y * (y - 1);
- if(x % 2 == 0) {
- ansi -= tor;
- } else {
- ansi += tor;
- }
- }
- cout << ((n * (n - 1)) / 2) - ansi << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement