HackerRank Number Theory – Mehta and his Laziness

Challenge: Mehta and his Laziness

Subdomeniu: Number Theory (number-theory)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464726497

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/mehta-and-his-laziness/problem

Cerinta

Mehta is a very lazy boy. He always sleeps in Maths class. One day his teacher catches him sleeping and tells him that she would mark him absent for the whole semester. While she pretends to be strict, she is actually very kind-hearted. So she wants to give Mehta a chance to prove himself. She gives him a problem. If Mehta can answer it correctly, she will forgive him. Can you help Mehta find the answer to this problem?  

The problem: The teacher gives Mehta a number $N$ and asks him to find out the probability that any proper divisor of $N$ would be an even perfect square.  

**Note: Even perfect square means the number should be even and a perfect square.**  

**Input Format**  
The first line of input contains an integer $T$, the number of test cases.   
$T$ lines follow, each line containing $N$, the number that the teacher provides.  

**Output Format**  
For each test case, print in a newline the output in $p/q$ format where $p$ and $q$ are positive coprime integers.  
if $p$ is 0, you should simply output `0`.  

**Constraints**  
$1 \le T \le 4 \times 10^4$  
$2 \le N \le 10^6$  

**Sample Input**

    4
    2
    8
    36
    900

**Sample Output**

    0
    1/3
    1/8
    3/26
    
**Explaination**  
For the first case $N = 2$, the set of proper divisors is $\{1\}$. Since $1$ is not an even perfect square, the probability is $0$.    
For the second case $N = 8$, the set of proper divisors is $\{1,2,4\}$ and only $4$ is an even perfect square among them, so probability = $1/3$.  
For the third case $N = 36$, the set of proper divisors is $\{1,2,3,4,6,9,12,18\}$, and only $4$ is an even perfect square, so probability = $1/8$.  
For the fourth case $N = 900$, there will be total of $26$ proper divisors and $3$ of them $\{4,36,100\}$ are even perfect squares.

Cod sursa

#include <bits/stdc++.h>
using namespace std;
long long int gcd(long long int a,long long int b)
{
    long long int r;
    while(b>0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    long long int i,j,k,l,m,n,o,p,t;
    long long int b[10001];
    
    cin>>t;
    while(t--)
    {
        cin>>n;
        l=0;
        j=sqrt(n);
        k=0;m=0;
        for(i=1;i<=(j);i++)
        {
           if(n%i==0)
           {
               b[l++]=i;
               k++;
               if((n/i)!=i&&i!=1)
               {
               k++;
               b[l++]=n/i;
               }
           }
        }
        sort(b,b+l);
        for(j=0;j<l;j++)
        {
            if(b[j]%2==0)
            {
                if(sqrt(b[j])==ceil(sqrt(b[j])))
                m++;
            }
        }
        
        if(m==0)
        cout<<0<<endl;
        else 
        {
            o=gcd(m,k);
            m=m/o;
            k=k/o;
           cout<<m<<"/"<<k<<endl;
        }
    }
    return 0;
}
/* 0
0 2 / 19 0 1 / 31 0 0 0 0 0 0 0 0 0 0 1 / 31 4 / 35 1 / 11 1 / 23 0*/