< Back to forum

https://www.codechef.com/problems/CK87QUER

I cant get the logic for the question in the above link .

I have seen a few submissions but why is it that summation of the values of A = no of pairs of A and B satisfying the given relation??

Asked by: Proma_Roy on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.


Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

The condition required is a^2+b<=y.

where, a can be any positive integer(non-zero)

and b varies from 1-700 inclusive.

we will exploit the fact here that b is bounded and can vary a for a given value of b.

So a^2<=(y-b) or a<=sqrt(y-b)

maximum value of a satisfying the above relation will be the floor value of sqrt(y-b) and 

numbers 1,2,3,4------,floor_value(sqrt(y-b)) will satisfy the above relation for that value of b.

So we just add all values of floor_value(sqrt(y-b)) for each b from 1-700(inclusive).

Here is the code,

#include<bits/stdc++.h>
using namespace std;
int  main()
{
    long long t;
    cin>>t;
    while(t--)
    {
        long long y,count=0;//since y can vary till 10^10
        cin>>y;
        for(int b=1;b<=700;b++)
        {
                if(y>b)//y should be greater than b else sqrt(y-b) will give wrong value
                {
                long long int numbers_of_a=floor(sqrt((double)(y-b)));
                count+=numbers_of_a;
                }
                
        }
        cout<<count<<endl;
    }
}

Anupam_Singh last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.