Square Function

general
1

Passing only one sub task

Problem Link : CodeChef: Practical coding for everyone

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MOD 1e9+7;


void init_code()
{
  fast_io;
  #ifndef ONLINE_JUDGE

  freopen("input.txt", "r", stdin);

  freopen("output.txt", "w", stdout);

  #endif // ONLINE_JUDGE
}

int N = 1e6;
vector<int> spf(N+1); // spf : smallest prime factor

int nc2(int n)
{
	return n * (n - 1) / 2;
}

set<int> get_odd_factors(int n)
{
	map<int,int> factors;

	while(n > 1)
	{
		factors[spf[n]]++;
		n = n / spf[n];
	}


	set<int> oddFactors;

	for(auto it : factors)
	{
		if(it.second % 2 == 1)
		{
			oddFactors.insert(it.first);
		}
	}

	return oddFactors;
}

void primeFactorization()
{
	// N log log N
	
	for(int i=1;i<=N;i++)
	{
		spf[i] = i;
	}

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

	// finding prime factors;

	// O(log n)
	// while(no != 1)
	// {
	// 	cout<<spf[no]<<" ";

	// 	no = no/spf[no];
	// }
}

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

  map<set<int>,int> freqs;

  for(int i=0;i<n;i++)
  {
  	int x;
  	cin>>x;

  	freqs[get_odd_factors(x)]++;
  }

  int ans = 0;

  for(auto it : freqs)
  {
  	ans += nc2(it.second);
  }

  cout<<nc2(n) - ans<<"\n";
}


int main()
{
  init_code();
  primeFactorization();

  int t;
  cin>>t;

  while(t--)
  {
    solve();
  }

  return 0;
}```
2

i didn’t code this way…i’m giving you my idea…
1st you make a pre-calculated array/vector where you keep the cube power to the maximum power below or equal 1e18 from 2 to 1000000(as (1e6)^3=1e18) and sort the pre calculated array…find the minimum square number that is nearest to the input and the maximum number that is smaller or equal to the input and minimum number that is greater or equal to the input by binary search…and which difference is minimum print the element (if more element has lowest different print the minimum)…