SQUAREFU - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Soumyadeep Pal
Tester : Radoslav Dimitrov
Editorialist: Aman Dwivedi

DIFFICULTY:

Simple

PREREQUISITES:

Observation, Prime Factorisation, Smallest Prime Factor

PROBLEM:

Let’s define a function F(X) as follows:

F(X) = \frac{X}{Y}

where Y is the largest perfect square that divides X.

You are given an array A consisting of N integers. A pair of integer (i, j) is called Good if 1 \leq i \lt j \leq N and F(A_i * A_j) \gt 1. Find the number of Good pairs.

EXPLANATION:

The first and basic observation is that F(X) is always greater than 1 if X is not a perfect square. When X is a perfect square then Y is equal to X and hence F(X) becomes equal to 1. In all other cases, Y will be always less than X, and hence the value of F(X) will be greater than 1.

So ultimately our goal is reduced to count such pairs (i, j) where A_i * A_j is not a perfect square. All such pairs will have F(A_i*A_j) greater than 1.

Let’s try to go opposite and try to find all such pairs (i, j) where A_i * A_j is a perfect square. After getting these pairs it is easy to find out those pairs where A_i * A_j is not a perfect square.

Now let’s see how we will be able to find all such pairs. Suppose we have two numbers A_i and A_j whose prime factorization looks like:

A_i = a^x * b^y
A_j = c^i * d^j

Now let’s look at the conditions when A_i*A_j is a perfect square:

  • If i,j,x and y are even, then the product is always a perfect square.

  • If some of the powers in A_i are odd then the same base should be present in A_j with power as odd. More formally if x is odd then either c=a or d=a with i and j as odd.

Hence we can divide our groups on the basis of those prime numbers that divide the integer odd number of times. For example, let us see the sample:

A= [2, 3, 12]

Now:

  • 2 is divisible by 2 odd number of times
  • 3 is divisible by 3 odd number of times
  • 12 is divisible by 3 odd number of times

Then there will be two groups:

  • Group 1: [2]
  • Group 2: [3, 12]

Now we can say that all the elements in the group will form pairs that have A_i*A_j as a perfect square. Hence we can easily count the total number of groups that have A_i*A_j as a perfect square

Since the value of N and T are large we can precompute for every integer I to which group it belongs, using the technique of Smallest Prime Factor.

Once we got the count of groups we can then simply found the total pairs where F(A_i * A_j) \gt 1.

TIME COMPLEXITY:

O(N*log(N)) per test case

SOLUTIONS:

Author
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int Nmax = 1e6 + 10;
int spf[Nmax]; //spf[i] = smallest prime factor of i
int oddprime[Nmax];
void SPF() {
	for (int i = 1; i < Nmax; i++) spf[i] = i;
	for (int i = 2; i * i < Nmax; i++) if (spf[i] == i)
			for (int j = i * i; j < Nmax; j += i) if (spf[j] == j)
					spf[j] = i;
}
map<int, int> get(int x) {
	map<int, int> ret; while (x != 1) { ret[spf[x]]++; x /= spf[x]; } return ret;
}
int n, check[Nmax], cnt[Nmax], a[Nmax];

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i] = oddprime[a[i]];
		cnt[a[i]] = 0;
		check[a[i]] = 0;
	}
	for (int i = 0; i < n; i++) {
		cnt[a[i]]++;
	}
	int ans = n * (n - 1) / 2;
	for (int i = 0; i < n; i++) {
		if (!check[a[i]]) {
			ans -= (cnt[a[i]] * (cnt[a[i]] - 1)) / 2;
			check[a[i]] = 1;
		}
	}
	cout << ans << '\n';

}

signed main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	SPF();
	for (int i = 1; i <= 1e6; i++) {
		map<int, int> m = get(i);
		oddprime[i] = 1;
		for (auto u : m) {
			if (u.second % 2 == 1) oddprime[i] *= u.first;
		}
	}
	int t; cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}
Tester
MAX = 10**6 + 42
lp = [0] * MAX

# Sieve
for i in range(2, MAX):
    for j in range(i, MAX, i):
        if lp[j] == 0:
            lp[j] = i


def solve_case():
    n = int(input())
    a = [int(x) for x in input().split()]

    cnt = dict()
    ans = n * (n - 1) // 2
    for x in a:
        v = 1
        squarefree_list = []
        while x > 1:
            flag = 0
            d = lp[x]
            while x % d == 0:
                flag ^= 1
                x //= d 

            if flag:
                squarefree_list.append(d)
       
        squarefree_list = tuple(squarefree_list)
        
        if squarefree_list not in cnt:
            cnt[squarefree_list] = 0
            
        ans -= cnt[squarefree_list]
        cnt[squarefree_list] += 1
        
    

    print(ans)


cases = int(input())
for _ in range(cases):
    solve_case()

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

#define int long long

const int mxN = 1e6+5;
int spf[mxN];
int odd_mul[mxN];

void SPF()
{
  for(int i=1;i<mxN;i++)
    spf[i] = i;

  for(int i = 2;i<mxN;i++)
  {
    if(spf[i]==i)
    {
      for(int j=i*i;j<mxN;j+=i)
      {
        if(spf[j] == j)
          spf[j] = i;
      }
    }
  }
}

void oddmul()
{
  for(int i=1;i<mxN;i++)
  {
    int x = i;

    map <int,int> m1;

    while(x!=1)
    {
      m1[spf[x]]++;
      x/=spf[x];
    }

    odd_mul[i] = 1;

    for(auto itr: m1)
    {
      if(itr.second%2==1)
        odd_mul[i]*=itr.first;
    }
  }
}

void solve()
{
  int n;
  cin>>n;

  int a[n];
  map <int,int> count,check;

  for(int i = 0;i<n;i++)
  {
    cin>>a[i];
    a[i]=odd_mul[a[i]];

    count[a[i]]++;
  }

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

  for(int i=0;i<n;i++)
  {
    if(check[a[i]]!=1)
    {
      ans -= (count[a[i]]*(count[a[i]]-1))/2;
      check[a[i]] = 1;
    }
  }

  cout<<ans<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);

  SPF();
  oddmul();

  int t;
  cin>>t;

  while(t--)
    solve();
}

Why does this code fail on the second testcase?

https://www.codechef.com/viewsolution/49867428

I basically just try to figure out how many numbers combined with the current one give perfect squares, by storing the factors that occur an odd number of times. I don’t see a testcase where it could go wrong. I’d appreciate the help. Thanks :slight_smile:

BTW, I’m aware that this could give TLE, but why the WA verdict?

You have initialized answer as int. answer can exceed int limit

1 Like

Thanks, it passed after all due to the bad tests though. :stuck_out_tongue:

1 Like

Here is my function, which will calculate the odd power multiple of every number in one go.

vi arr(maxN, 1);
void fun(){
ffor(i, 2, maxN){
int x = sqrt(i);
if (arr[i] == 1 && x * x != i){
for (int j = 1; j * j * i < maxN; j++){
arr[j * j * i] = i;
}
}
}
}
Any suggestion/Query are welcomed.

Why bad tests

I guess he is pointing towards getting an AC with \mathcal{O}(N \log^2N) solution.

3 Likes

It’s not an O (N \log^2 N) which should be at the edge of passing, but an O (N \sqrt{N}), which definitely shouldn’t pass. For example, let every number be equal to 997^2, it clearly takes about 10^9 operations just to do the prime factorization in the worst case (10 tests with 10^5 numbers each).

1 Like

True… I checked your code now, it’s actually O(N \sqrt {A_{\text{max}}}) which shouldn’t pass, I presumed yours was an \mathcal{O}(N\log^2 A_{\text{max}}) after my solution with the same complexity passed unexpectedly in 0.33 seconds.

Last two questions do not have editorial with them. @cherry0697, @soumyadeep_21 .

Today’s Night. It was sudden and unfortunate dizziness attack which leads to me hospital. Just got back home today in morning, will write those today’s night.

1 Like

I gave one test n=1e5, a(i)= 9e5 +1 to 10e6. Actually in cc 10^8 operations easily passes - .2 sec unlike cf. I forgot that. Tester also did not point out that.

Notice that if we find S_i, the largest square that divides each A_i, and calculate the "square-free part of A_i" as B_i = A_i/S_i, then we have:

B_i = B_j \iff F(A_i\cdot A_j) = 1

Then for the given data size it makes sense to precalculate \{S_i\} across the range with a sieve-type approach, and we can then count up different values of B_x as we receive A_x values. Then we can calculate good pairs directly, since every number with a given B_i will only make good pairs with numbers with a different B value.

from sys import stdin
from collections import Counter

lim = 1000000
gsq = [1]*(lim+1)
val = 2
sq = 4
while sq <= lim:
    gsq[sq::sq] = [sq] * (lim//sq)
    val += 1
    sq = val*val

# ===================== #

T = int(input())
for tx in range(T):
    N = int(stdin.readline())
    diff_sf = Counter(a//gsq[a] for a in map(int, stdin.readline().split()))
    print( sum(d*(N-d) for d in diff_sf.values())//2 )

Solution: 49989389 | CodeChef

I am not able to figure out that why my solution is failing test case 2. Please help