Yet Another Sum Problem
Practice
5 (1 votes)
Problem
20% Success 210 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code
You are given an integer \(N\).
Find the sum of \(\lfloor \frac{i}{j} \rfloor\) for all pairs of \(i\),\(j\) ( \(1 \leq i \leq N\) and \(1 \leq j \leq N\)), such that \(i\) and \(j\) are co-prime.
Input Format:
A single line contaning an integer \(N\).
Constraints:
\(1 \leq N \leq 10^5\)
Output format:
Print the required sum.
Sample Input
5
Sample Output
21
Explanation
floor(1/1)+floor(2/1)+floor(3/1)+floor(3/2)+floor(4/1)+floor(4/3)+floor(5/1)+floor(5/2)+floor(5/3)+floor(5/4)=21
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Submissions
Please login to view your submissions
Similar Problems
Points:30
3 votes
Tags:
MathHashmapSieveNumber TheoryInteger FactorizationAlgorithmsDatastructuresBasic Math
Points:30
5 votes
Tags:
MathematicsDynamic programmingMediumNumber TheoryFactorization
Points:30
1 votes
Tags:
mathsprime factorizationsieveMedium
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor