Solution 3 for Scaler Topics Fortnightly Contest - 13

This article is part of the Scaler Topics Fortnightly Contest - 13

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

• Now, we have to find out the number of possible arrays (of size A consisting of values between 1 and B inclusive) such that their GCD is G (1 <= G <= B).
• For an array to have GCD as G, all the elements should be divisible by G i.e all the elements should be multiples of G. But if all the elements are mutliples of k * G (k > 1) as well, their GCD is k * G not G.
• Let counts[G] denote the count of possible arrays (of size A consisting of values between 1 and B inclusive) such that their GCD is G.
• Number of arrays (of size A consisting of values between 1 and B inclusive) such that all elements are multiples of G = pow(B/G,A).
• Hence counts[G] = pow(B/G,A)- counts[2 * G] - counts[3 * G] …
• If we calculate counts in reverse order (i.e. for B to 1), we can easily calculate for each G.
• Pseudo-Code: ans=0 for G in range(B,0,-1): cnt=pow(B//G,A,mod) for j in range(1,B//G+1): cnt=(cnt-counts[Gj])%mod counts[G]=cnt ans=(ans+(Gcnt)%mod)%mod
• Time Complexity Both loops run in: O(B/B + B/(B-1) + … + B/2 + B/1) = O(B * log(B)) Calculating pow(x, y, mod) would take O(y) time using Modular Exponentiation. Hence, Total- O(B * (log(B) + log(A))
• Space Complexity - O(B)

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation