The Easiest Problem

Tareq_Abrar CPC Programming Contest 2...
Limits 1s, 512 MB

Tareq Abrar is a lazy programmer. He has a friend named Aminvai, who is famous for his amazing skills. Aminvai has a lot of followers & a fan club. Once, Tareq gave him a problem to solve. But Aminvai was busy with his newly married wife. So, Tareq was very sad finding no way to solve the problem. Actually, it was very easy task. But Tareq Abrar is a lazy boy. So he told you to solve the problem. If you solve the problem, you will be considered as a helpful friend of Tareq. So, let's help Tareq.

You will be given two positive integers $N$ and $X$. You have to observe all positive integers M
so that $M<NX$ and M, N are relatively prime. If N and X are given, you've to answer the sum of all such M positive integers.

Two positive integers A and B are called relatively prime if $GCD(A, B) = 1$.

So, this is very easy problem. I think you will be able to help our lazy friend Tareq. 🙂


There are several test cases. The first line of input contains a positive integer $T$ ($ 1 \le T \le 5 \times 10^5 $) , which denotes the number of test cases.

In each line of next $T$ lines, there will be given two positive integers $N$ ($ 2 \le N \le 10^4 $) and $X$ ($ 1 \le X \le 10^4 $) separated by space.


Output will contain $T$ lines. In each line, you have to print a positive integer which denotes the answer.


5 1
4 2
9 3
7 1
100 2

Details: For the first test case

NX = 5* 1 = 5

All such positive integers M are 1, 2, 3, 4 : so that (M,N)=1 and M< NX.

Sum of these are: 1+2+3+4 =10


Login to submit.


40% Solution Ratio
YouKnowWhoEarliest, May '20
HKShakibFastest, 0.1s
YouKnowWhoLightest, 7.3 MB
steinumShortest, 339B
Toph uses cookies. By continuing you agree to our Cookie Policy.