YAE - Editorial

editorial
, , , , , ,
1

Contest

Author: Rahul Sharma

Tester: Sumukh Bhardwaj

Editorialist: Rahul Sharma

DIFFICULTY:

Easy-medium

PREREQUISITES:

Number-theory, math, pre-processing, observation, count array, ad-hoc

PROBLEM:

Given a positive integer A, find the total number of ordered pairs (B,C) such that A+B^{2C} is any perfect square, where B and C are positive integers ranging between 1 to 10^5.

QUICK EXPLANATION:

Find all pairs of factors of A. Let pair (F1, F2) if (F2-F1) mod 2 is 0 then B^C = |F1 -F2|/2. Let Y = |F1 - F2|/2 then possible pairs (B,C) such that (B,C) = Y can be found in O(sqrt(Y) \times log(Y)) time complexity.

EXPLANATION:

Subtask #1:
Run two nested loops outer loop for B and inner loop for C and check for each possible pair (B,C) for given range and store the answer. It will pass only subtask #1.

Subtask #2:
Let us make some simplification and observe it. Let A+B^{2C} = X^2

A = X^2 - B^{2C}
A = (X - B^C)(X + B^C)

From above we are sure that (X - B^C) and (X + B^C) are pair of factors of A. Let small factor be F1 and other F2

F1 \times F2 = (X - B^C)(X + B^C)
F1 = X - B^C _________eq(i)
F2 = X + B^C__________eq(ii)

Subtract eq(i) from eq(ii)

2 \times B^C = F2 - F1
B^C = (F2 - F1)/2

Since B and C are integers therefore (F2 - F1) must be divisible by 2.
Let (F2-F1)/2=Y

B^C = Y

Iterate B from 2 to sqrt(Y) and for each B_i, C_i = log_{B_i}(Y). It will give all possible pairs for (B,C).

Since test cases are 10^6. To avoid TLE preprocessing can be done and results can be stored such that each test case can be answered in O(1) time complexity.

Following are the steps of preprocessing:

  1. For every number i between 1 to 10^5 store the count of pairs (B,C) such that B^C=i in array pairCount at index i.
  2. For A iterate i from 1 to 10^5. Sum up count by directly loking up at pairCount for all valid Y for each A_i and store it in array ans at index i.

Now read test case and for each test case lookup at the index in ans array directly and print that answer.

Few Corner Cases:
A=8 answer is 10^5. (When B^C = 1)
A=1 answer is 0.

This solution will pass all subtasks

COMPLEXITIES

For all subtasks to pass

TIme Complexity:
Preprocessing - O(N*sqrt(N)*log(N) + N*sqrt(N)) where max(N) = 10^5
Each test case - O(1)

Space Complexity: O(M) where M=10^5

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

int arr[100005], ans[100005];

int lg(int a, int b)
{
	int count = 0;
	while(a>1)
	{
		a = a/b;
		++count;
	}
	return count;
}

int pwr(int a, int b)
{
	if(b==0)
		return 1;
	if(b==1)
		return a;
	int res = 1;
	while(b>0)
	{
		if(b&1)
			res = res*a;
		b = b>>1;
		a = a*a;
	}
	return res;
}

int pairCount(int a) 
{ 
    if (a == 1) 
        return true; 
  	int count = 0, i;
    for (i = 2; i * i <= a; i++) { 
        int val = lg(a,i); 
        if (pwr(i,val) == a) 
            ++count; 
    } 
    return count; 
} 

int calAns(int a)
{
	int i,ans = 0, val;
	for(i = 1; i*i <= a; ++i)
	{
		if(a%i == 0)
		{
			val = a/i - i;
			if(val%2 == 0)
			{
				val = val/2;
				ans = ans + 1 + arr[val];
			}
		}
	}
	return ans;
}
int main()
{
	int n = 100000, i, t, a;
	arr[0] = -1;
	arr[1] = 99999;
	for(i = 2; i <= n; ++i)
		arr[i] = pairCount(i);	
	for(i = 1; i <= n; ++i)
		ans[i] = calAns(i);
	cin>>t;
	while(t--)
	{
		cin>>a;
		cout<<ans[a]<<endl;
	}
}
4 Likes