Find number of pairs such that their GCD = g.

Problem: 

n(<=1e5) সাইজের একটি অ্যারে a দেয়া থাকবে যেখানে a[i]<=1e5 এবং q(<=1e5) টি কুয়েরী থাকবে। প্রতি কুয়েরী তে একটি সংখ্যা g দেয়া হবে। বলতে হবে অ্যারে তে এমন কয়টি পেয়ার (i,j) আছে যাদের GCD(a[i] , a[j]) = g এবং i<j

আইডিয়াঃ

১) প্রথমত, আমরা চেষ্টা করবো এমন কয়টা পেয়ার সম্ভব যাদের GCD g অথবা এর মাল্টিপল। এই কাজটি আমরা কিভাবে করতে পারি? 

১ থেকে ১০^৫ পর্যন্ত সবার ফ্রিকুয়েন্সি কাউন্ট করে রাখবো। এরপর, প্রতিটি সংখ্যার জন্য তার সম্ভাব্য সকল মাল্টিপল এর ফ্রিকুয়েন্সি যোগ করে পাবো এমন কয়টি সংখ্যা আছে যা ঐ সংখ্যা দ্বারা ভাগ যায়। 

এখন, x দ্বারা বিভাজ্য এমন মোট অ্যারে এলিমেন্ট y হলে, y C 2 বা (y*(y-1))/2 টি পেয়ার আছে যাদের GCD x অথবা তার মাল্টিপল। 

২) এখন, প্রতিটি সংখ্যা x এর জন্য এক্সেক্ট কতোগুলো পেয়ার আছে যাদের GCD = x এই কাজটি সহজেই করা যাবে।