আলোচনাঃ
ধরা যাক, আমাকে N=5 দিল। তাহলে প্রশ্ন অনুসারে আমাদের বের করা লাগবে যে,
LCM(1,5)+LCM(2,5)+LCM(3,5)+LCM(4,5)+LCM(5,5) = 5+10+15+20+5 = 55
এখানে N এর মান যেহেতু খুব কম তাই প্রথমে (1,5) ,(2,5), (3,5) , (4,5), (5,5) এদের gcd বের করে সেখান থেকে lcm বের করে যোগ দিলেই হবে।
কিন্তু আমাদের প্রশ্নে দেওয়া N = 1000000 আর T = 300000. এর মানে brute force করতে গেলে যে TLE খাবো তা নিশ্চয়ই বুঝতে পারছো ? তাহলে কি করা যায়?
উত্তরঃ
আসলে এটা বের করার একটা সূত্র আছে। সূত্রটা হচ্ছে –
∑LCM(i, n) = (( ∑(d * ETF(d)) + 1) * n) / 2 —–(1)
সূত্রের প্রমাণ দেখতে চাইলে এই অথবা এই লিংক থেকে দেখে নিতে পারো।
এখানে ETF = Euler totient function. Euler totient function বলতে বুঝায় , 1 থেকে N পর্যন্ত কতগুলো সংখ্যা (i) আছে, যাদের সাথে ‘N’ এর gcd(i,N) = 1 হয়। তো আমরা N পর্যন্ত Euler totient function কিভাবে pre-calculate করতে হয় সেটা জানি। অনেকটা sieve এর মতোই। আর এর Complexity হলো O(Nlog(logN)
| i | 1 | 2 | 3 | 4 | 5 |
| Phi[i] | 1 | 1 | 2 | 2 | 4 |
উপরের টেবিল এ N = 1 to 5. তার মানে ,
i=1 থেকে N=1 পর্যন্ত কতগুলো number আছে ,যাদের সাথে N এর gcd=1–> ans=1
i=1 থেকে N=2 পর্যন্ত কতগুলো number আছে ,যাদের সাথে N এর gcd=1–> ans=1
i=1 থেকে N=3 পর্যন্ত কতগুলো number আছে ,যাদের সাথে N এর gcd=1–> ans=2
i=1 থেকে N=4 পর্যন্ত কতগুলো number আছে ,যাদের সাথে N এর gcd=1–> ans=2
i=1 থেকে N=5 পর্যন্ত কতগুলো number আছে ,যাদের সাথে N এর gcd=1–> ans=4
তো এই মান গুলো কিভাবে পেলাম?
আমরা জানি,
If, n = p1^a1 * p2^a2 * p3^a3
Then,
ETF(n) = n*(1-(1/p1))*(1-(1/p2))*(1-(1/p2))—(2)
=> ETF(n) = n-(n/p1)…..—(3)
এখানে (2) এর (1-(1/p1)) কে যদি আমরা n এর সাথে গুণ করে দেই তাহলে (3) পাই। আর এই (3) no derivation টাই আমরা program এ লিখব (phi[j]-= phi[j]/i) । কারণ গুণ করতে computer বেশি টাইম নেয়।
বিঃদ্রঃ এই প্রবলেম solve করার জন্য Euler Phi সম্পর্কে ভালোভাবে জানা থাকতে হবে। যেহেতু problem নিয়ে লিখছি তাই theory নিয়ে আর বেশি আলোচনা করলাম না।
এখন আমাদের প্রবলেমে ফিরে আসি।
(d * ETF(d)) এখানে ‘d’ হচ্ছে N এর divisor. তার মানে N এর divisor এর euler phi বের করে তার সাথে divisor কে গুণ দেয়া লাগবে। তার মানে এখানে N এর divisor গুলোও বের করা লাগবে। তো আমরা নিচের উপায়ে 1-N পর্যন্ত সকল নম্বর এর divisor বের করতে পারি।
const int N=1e5+10;
vector<int> div[N];
void findDivisor(){
for(int i=1;i<=N;i++){
for(int j=i;j<=N;j+=i){
div[j].push_back(i);
}
}
}
ধরা যাক, N=10 এর হলে তার divisor 1,2,5,10 কে 10 এর মধ্যে push করছি। তো আমরা এখানে N এর একটা divisor বের করে সাথে সাথেই সেই divisor এর ETF(d) বের করে তার সাথে ‘d’ গুণ করতে পারি।
আর যেহেতু summation of ∑(d * ETF(d) বের করতে হবে তাই একই সাথে যোগ করতে থাকবো। এটা করতে পারলেই আসল কাজ করা শেষ। আর বাকি রইল সূত্র অনুযায়ী যোগ,গুণ,ভাগ করা। এটা করতে পারলেই আমরা প্রতিটা query O(1) এ বের করে ফেলতে পারবো।
একেবারে শুরুর উদাহরণটা এবার উপরের উপায়ে করে দেখি যে সঠিক উত্তর দেয় কিনা।
divisors of 5 = 1,5
So, ((( (1*ETF(1) + 5*ETF(5)) + 1 )*n)/2)
=>((( (1*1 + 5*4) + 1 )*n)/2) [ as phi[1]=1, phi[5]=4 ]
=>((( (1 + 20) + 1 )*5)/2)
=>(22*5)/2
=> 55 ; যা মিলে যাচ্ছে
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll phi[N];
ll ans[N];
/// ∑LCM(i, n) = ((∑(d * ETF(d)) + 1) * n) / 2
void ETFPre(){
for(ll i=0;i<=N;i++){ // O(Nlog(logN))
phi[i]=i;
}
for(ll i=2;i<=N;i++){
if(phi[i]==i){
for(ll j=i;j<=N;j+=i){
phi[j]-= phi[j]/i;
}
}
}
for(ll i=1;i<=N;i++){ // O(NlogN)
for(ll j=i;j<=N;j+=i){
ans[j]+= (i*phi[i]); // ∑(d * ETF(d) , here i = divisor of j
}
}
}
int main(){
ETFPre();
ll n;
int t;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
ll res=((ans[n]+1)*n)/2; // formula
printf("%lld\n",res); // O(1)
}
}
Related Problem – Odd Numbers of Divisors , False Ordering