Holi and Division Function
Tag(s):

## Easy-Medium, Mathematics, Number Theory, Number theory

Problem
Editorial
Analytics

Monk is very busy with a problem and he has to leave for the celebration of Holika Dahan. He asks you to help him with the problem so that he can enjoy with his friends.

Let us define the division function F(n) as:

If Decimal part of n is >=0.5 we take ceil of n else we take floor of n.


Eg. F(4.51)=5, F(4.49)=4.

Given an array A of size N . Compute the all pair division function.

ans=0;
For(i=0;i<N;i++)
{
For(j=0;j<N;j++)
{
ans=ans+F(A[i]/A[j])
}
}
return ans;

Input Format

First line contains an integer T denoting the number of test cases.

Each test case contains two lines:

First line contains an integer N.
Next line contains N space separated integers denoting array A.

Output Format:

For each test case, print the value returned from all pair division function.

Input Constraints:

$1 \le T \le 10$

$1 \le N \le 10^5$

$1 \le A[i] \le 10^5$

SAMPLE INPUT
1
3
1 2 3
SAMPLE OUTPUT
12

Explanation

F(1/1)=1 F(1/2)=1 F(1/3)=0

F(2/1)=2 F(2/2)=1 F(2/3)=1

F(3/1)=3 F(3/2)=2 F(3/3)=1

The sum is $12$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

March Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming

?