Akash and GCD 1

Problem link: Akash_gcd_1

We need to perform query based on given function F, that

F(x) = GCD(1, x) + GCD(2, x) + ..... + GCD(x, x)
Where GCD is the Greatest Common Divisor
Now in the problem, given an array A of size N, there are 2 types of queries:

1. C X Y: Compute the value of F(A[X]) + F(A[X+1]) + F(A[X+2]) + .... + F(A[Y]) (mod 10^9+7)
2. U X Y: Update the element of A[X] = Y

Solution:

At first we need to pre compute the value of F(x). Also we need help of Euler's Totient Function for this purpose. You can learn Euler Totient from here: Euler's Totient
Also we need to compute summation of GCD(i,n) for i = 1 to n. If you don't know how to do that, see here: GCD summation

This problem can be solved by segment tree. But as we only need prefix sum and simple update query, we can also solve it using binary indexed tree. As binary indexed tree is easy to code and simple, it's preferable.

Code:

Notice at line 86, the computed value might go negative less than 10^9+7. So we used a while loop to check while the value is below zero, we will add the mod value to make it positive. If we checked the negative value mod in the qeury function, this wouldn't be necessary.

Calculate Summation of GCD(i,n); for i = 1 to n

আমাদের এবারের কাজ হল ১ থেকে n পর্যন্ত সবগুলো সংখ্যার সাথে n এর গ.সা.গু. বের করে তাদের যোগফল বের করা।

শুনতে ব্যাপারটি সহজ মনে হলেও, আসলে ঠিক সহজ না, যদি না আমরা সঠিক এপ্রোচ না জানি। নরমালি আমরা যখন প্রোগ্রামিং এ নতুন, তখন আমরা ১ থেকে n পর্যন্ত লুপ চালায়ে তাদের যোগফল বের করতাম।



এখন কথা হচ্ছে, এভাবে করলে আমরা বড় বড় সংখ্যার জন্য আমরা TLE খাবো। যেমন n = 1000000000 এর জন্য আমাদের প্রচুর সময় লাগবে, ( ইচ্ছে করলে উপরের কোডটি নিজ দায়িত্বে রান করে দেখে নিতে পারো :3 )
এখন তাহলে আমরা কিভাবে এর সমাধান করবো? খেয়াল করলে দেখবো যে, আমরা যখন ১ থেকে n পর্যন্ত স্বাভাবিক সংখ্যাগুলোর সাথে n এর গসাগু বের করার চেষ্টা করছি,তখন আসলে আমরা প্রতিবার n এর সবগুলো বিভাজক( all divisor ; there maybe multiple occurance of divisors) নিয়ে তাদের যোগফলটা নিচ্ছি। যেমনঃ  n = 8 হলে, gcd(1,8) + gcd(2,8) + gcd(3,8) + gcd(4,8) + gcd(5,8) + gcd(6,8) + gcd(7,8) + gcd(8,8)  = 1+2+1+4+1+2+1+8 = 20।
এখানে খেয়াল করে দেখি যে, আমরা কিন্তু ১,২,৪,৮ ছাড়া আর কিছু যোগ করছিনা! আর এই সংখ্যাগুলি কিন্তু আসলে ৮ এর বিভাজক (divisor)। আমরা আপাতত গোনায় বাদ রাখলাম কোন সংখ্যা কতবার নিচ্ছি, কিন্তু আসল কথা হচ্ছে আমরা n এর divosr গুলিকেই নিচ্ছি আমাদের ক্যাল্কুলেশন এর জন্য। তাহলে বুঝা যাচ্ছে আমাদের আসলে n এর divisor গুলি বের করতে হবে। আর আমরা O(√n) কমপ্লেক্সিটি তে n এর divisor বের করতে পারি। কাজেই, n = 1000000000 এর জন্য আমরা 31622.77.. কমপ্লেক্সিটিতে divisor গুলি বের করে, এরপরে আমাদের বাকি কাজ করবো।
তাহলে  n = 8 এর জন্য, আমাদের যোগফল অনেকটা এরকম হবে দেখতেঃ

এখানে coef1,coef2... এগুলোই আমাদের বের করতে হবে। divisor গুলি আমরা আগেই পেয়ে গেছি।
১ থেকে n পর্যন্ত সংখ্যাগুলোর সাথে n এর গ.সা.গু. বের করতে গেলে,গ.সা.গু = ১ কতবার আসবে, সেই সংখ্যাটা আসলে n এর অয়লার ফাংশন। অয়লার ফাংশন সম্পর্কে না জানলে এই লিঙ্ক দেখার অনুরোধ রইল আগে।
আচ্ছে এখান থেকে আমরা একটু মনযোগ দেয়ার চেষ্টা করি,

phi (8) = 4.
phi (4) = 2.
phi (2) = 1.
phi (1) = 1.
আমরা এখানে আসলে ৮ এর divisor গুলির phi এর মান দেখলাম।
আচ্ছে এখন দেখা যাক, phi(8) = 4 এর জন্য, কোন কোন জোড়া নিলে আমাদের গসাগু ১ আসছেঃ
(1,8), (3,8), (5,8), (7,8); কাজেই, আমাদের coef1 = 4 হবে।

( coef1*(1); এই 1 এর মানে হচ্ছে, ঐসব জোড়া আমরা নিবো, যাদের মাঝের গ.সা.গু. = 1 হবে, এরকম জোড়া আছে 4 টি, কাজেই আমাদের coef1 = 4 )
এখন আমরা বের করবো coef2 এর মান। কাজেই আমাদের বের করতে হবে এমন কতটি জোড়া আছে, যারা 8 এর সাথে গ.সা.গু.  = 2 হবে। এজন্য আমাদের দরকার phi(8/2) = phi(4) এর মান। আমরা আগেই বের করে রেখেছি, phi(4) = 2. কাজেই আমাদের coef2 = 2. একইভাবে, coef3,coef4 বের করতে পারবো আমরা। ফাইনালি,
coef1 = phi(8/1) = phi(8) = 4. ; divide by first divisor = 1.
coef2 = phi(8/2) = phi(4) = 2. ; divide by second divisor = 2.
coef3 = phi(8/4) = phi(2) = 1. ; divide by third divisor = 4.
coef4 = phi(8/8) = phi(1) = 1. ; divide by forth divisor = 8.


কাজেই, আমাদের ফাইনাল রেজাল্ট ঃ

phi(8/1)*1 + phi(8/2)*2 + phi(8/4)*4 + phi(8/8)*8
= 4*1 + 2*2 + 1*4 + 1*8 = 20 

অ্যালগরিদম (Algorithm)

without pre computing phi values:


এখন আমাদের অনেক কুয়েরি থাকলে আমাদের আগে থেকে phi এর মান বের করে রাখতে হবে। ঐ ব্যাপারটা তোমরা নিজেরা করে দেখো। আবার যদি আমাদের n এর মান অনেক বড় হয়ে যায় যে, আমরা O(√n) এও TLE খাচ্ছি, তাহলে আমাদের number theorem এর অন্যরকম এপ্রোচ নিতে হবে। এগুলো নিয়ে পরে আলোচনা করা যাবে। 

Euler's Totient or Phi Function φ(n)

phi ফাংশন কি?

phi ফাংশন একটি arithmetic function যেটি count করে একটি সংখ্যা N এর সমান বা ছোট কতটি ধনাত্মক সংখ্যা আছে যেগুলো N এর  সহমৌলিক (relative prime). অর্থাৎ 1 থেকে শুরু করে N পর্যন্ত মোট কতটি সংখ্যা আছে যেগুলোর সাথে N এর 1 বাদে অন্য কোন সাধারন উৎপাদক (common divisor) নেই, আরেকটু সহজ করে বলতে গেলেঃ 1 থেকে N এর মাঝে, যাদের সাথে N এর GCD = 1. উদাহরন :
15 সংখ্যাটি বিবেচনা করি,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
এর মধ্যে থেকে 15 এর সাথে common divisor আছে এমন সংখ্যাগুলোকে মার্ক করিঃ
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
এই সংখ্যাগুলিকে বাদ দিবো, কেননা 15 এর গুননীয়ক ঃ 3 এবং 5. কাজেই, এদের গুনিতক (3, 5, 6, 9, 10, 12, 15) এগুলো বাদ যাবে।
তাহলে অবশিষ্ট থাকে 8 টি সংখ্যা – 1, 2, 4, 7, 8, 11, 13, 14
সুতরাং, φ( 15 ) = 8.
এখন চিন্তা করি, মৌলিক সংখ্যার জন্য phi এর মান কত হবে?
খেয়াল করলে দেখবো যে, আসলে কোন মৌলিক সংখ্যার সাথে তার আগের সকল সংখ্যাই সহমৌলিক, অর্থাৎ এদের মাঝে ১ ছাড়া আর কোন গুননীয়ক নেই। অর্থাৎ, φ(প্রাইম) = প্রাইম - ১।
7 সংখ্যাটি একটি prime number. তাহলে 7 এর জন্য,
1, 2, 3, 4, 5, 6, 7
so, φ(7) = 7-1 = 6.
so, φ(prime) = prime-1

মৌলিক সংখ্যার ক্ষেত্রে কাজটা অনেক সহজ হলেও অন্যান্য ক্ষেত্রে কিছুটা জটিল। এজন্য আমাদের একটি Theorem জানতে হবে। সেটি হলঃ
φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime

এর জন্য, আমাদের i এবং j, উভয়কেই সহমৌলিক হতে হবে। এখন খেয়াল করি, আমরা যদি, i এবং j কে এমনভাবে নিয়ে আসতে পারি, যে তারা উভয়েই প্রাইম হবে, অর্থাৎ যেকোন সংখ্যাকে আমরা প্রাইম এর ফ্যাক্টরে নিয়ে আসতে যদি পারি, তাহলে আমাদের জন্য φ(prime) = prime-1 দিয়ে প্রতি প্রাইম ফ্যাক্টর এর phi বের করা খুবি সহজ, এবং সেখান থেকে φ( i*j ) = φ( i ) * φ( j ) এই ফর্মুলার মাধ্যমে আমরা প্রাইম ফ্যাক্টর থেকে প্রাপ্ত phi এর মান গুন করে দিলেই মূল সংখ্যার phi এর মান পেয়ে যাবো। উদাহরনঃ

φ( 30 ) = φ( 2 ) * φ( 3 ) * φ( 5 )
now, φ( 2 ) = 1, φ( 3 ) = 2, φ( 5 ) = 4.
so, φ( 30 ) = 1 * 2 * 4 = 8
অর্থাৎ 1 থেকে 30 এর মাঝে, 30 এর সাথে সহমৌলিক 8 টি সংখ্যা আছে।
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
এগুলো হলঃ 1, 7, 11, 13, 17, 19, 23, 29 (Total 8 numbers).

এখন ধরা যাক, আমরা 4-এর φ ফাংশনের মান বের করতে চাই। আমরা এখন পর্যন্ত যা জানি, তা অনুযায়ী,
 φ(4) = φ(2)*φ(2) = 1*1 = 1.
কিন্তু ,
GCD(1,4) = 1, রিলেটিভলি প্রাইম
GCD(2,4) = 2
GCD(3,4) = 1, রিলেটিভলি প্রাইম
GCD(4,4) = 4
অর্থাৎ, φ(4) = 2
এটি কিন্তু আমাদের ফর্মুলা অনুযায়ী মিলেনি। তাহলে আমরা এখান থেকে একটি জিনিস খেয়াল করতে পারি যে, যখন আমাদের প্রাইম ফ্যাক্টরের ঘাত (power) ১ হবে, কেবলমাত্র তখনি আমরা আমাদের উপোরক্ত ফর্মুলা ব্যবহার করতে পারবো। তাহলে এরকম ক্ষেত্রে আমাদের ফর্মুলার একটু পরিবর্তন আসবে এভাবে ঃ
φ( n^k ) = n^k – n^k-1 , when n is prime and k != 1.
তাহলে আমরা এতক্ষনের আলোচনা থেকে ৩ টি গুরুত্বপূর্ণ ব্যাপার দেখলাম। এগুলি হলঃ 

1. φ( n ) = n - 1, when n is prime and power is 1.
2. φ( n^k ) = n^k – n^k-1 ,when n is prime and k != 1.
3. φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime.

অ্যালগরিদম (Algorithm)

আমরা 1 থেকে N পর্যন্ত লুপ চালায়ে ব্রূট ফোর্স অ্যালগরিদম লিখতে পারি এভাবেঃ

কিন্তু এটি বড় বড় সংখ্যার জন্য রান করতে অনেক সময় নিবে, কাজেই এটি তেমন ভালো এপ্রোচ না আমাদের জন্য।
এবার আমরা একটু অন্যভাবে প্রোগ্রাম করবো।
৩৬ = (২*২)*(৩*৩)
φ(৩৬) এর সর্বোচ্চ মান হতে পারে ৩৬। কাজেই আমরা ইনিশিয়ালি, result = 36 লিখে রাখবো।
এর মৌলিক গুণনীয়ক আছে দুইটিঃ ২ এবং ৩। এখন,
১ থেকে ৩৬-এর মধ্যে ২-এর গুণনীয়ক কয়টি আছে?  উত্তরঃ ৩৬/২ = ১৮ টি।
তাহলে, আমরা লিখবো result = result - 18 = 36 - 18 = 18.
এখন আমরা ৩৬ কে ২ দিয়ে যতবার ভাগ করা যায়, করে ফেলবো। এক্ষেত্রে ২ বার ভাগ করার পরে আমরা পাবো ৯।
এখন ১ থেকে ১৮ এর মাঝে ৩ এর গুণনীয়ক আছে , ১৮/৩ = ৬ টি।
তাহলে আমরা লিখবো result = result - 6 = 18 - 6 = 12.
সুতরাং, φ(৩৬) = ১২।
এরপরে আমরা আবার ৯ কে ৩ দিয়ে ভাগ করতে থাকবো। যদি আমাদের n এর মান ১ হয়ে যায়, তাহলে আমাদের আর কিছু করার দরকার নাই। কিন্তু যদি ১ না হয়, তাহলে আমরা result = result - result/n করবো, কেননা, ১ যেহেতু হয়নি, কাজেই, n আসলে প্রাইম নাম্বার ছিল। আর আমরা আগেই জানি, প্রাইম এর জন্য φ(prime) = prime-1

এতক্ষন আমরা যেসব phi জেনারেট করলাম, তার সবই সিম্পল কুয়েরির ক্ষেত্রে ভালো এবং দ্রুত আউটপুট দিবে, কিন্তু, আমাদের যদি কুয়েরির মান অনেক হয়, তাহলে বারবার phi ফাংশন কল করলে আমাদের প্রোগ্রাম TLE দিবে। এজন্য আমাদের আরও এফিশিয়েন্ট অ্যালগরিদম দরকার, যার মাধ্যমে আমরা সহজে অনেকগুলি phi এর মান আগে থেকে জেনারেট করে এরপরে কুয়েরির অ্যান্সার করবো। ঠিক সীভ (sieve of eratosthenes) যেভাবে জেনারেট করতাম, সেভাবে জেনারেট করবো। সকলের জন্য পরামর্শ রইল নিজে কোডটি লিখার। চেষ্টা করার পরে না পারলে এরপরে নিচের কোড দেখে শিখে নেয়া যাবে।

ফাইনালি, একটি সুন্দর জিনিস দেখা যাক।
"For any integer n, the sum of the totient(phi) values of each of its divisors equals n".
এখন দেখা যাকঃ
n = summation of φ( x ) ; where x are the divisors of n.
যেমন, 30 এর divisor =
1 x 30
2 x 15
3 x 10
5 x 6
so,  30 = φ( 1 )+φ( 2 )+φ( 3 )+φ( 5 )+φ( 6 )+φ( 10 )+φ( 15 )+φ( 30 ) = 1+1+2+4+2+4+8+8 = 30
অর্থাত, যেকোন সংখ্যার সকল divisor এর phi এর মানের যোগফল, ঐ সংখ্যার সমান হবে।

Practice Problems

• phi-phi-phi (medium)
• Monk and ETF (hard)