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:
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:
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();
}
