 # SQUAREFU - Editorial

Editorialist: Aman Dwivedi

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: 
• 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 =  * 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 BTW, I’m aware that this could give TLE, but why the WA verdict?

1 Like

Thanks, it passed after all due to the bad tests though. 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.

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 = *(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):