Faktorial, dərəcələr və abel qrupları
Mətn boyunca f(n) ilə n tərtibində izomorfizmə qədər Abel qruplarının sayını təyin edək. m və N sabit təbii ədədlər olsun. L və R təbii ədədlərindən ibarət bir neçə cüt üçün, L ≤ R ≤ N şərtini ödəyən, aşağıdakı cəmin qiymətini tapmaq lazımdır.
Abel qrupları ilə bağlı əsas anlayışları və faktları xatırladaq.
Abel qrupu G=(A,*) cütüdür, burada A müəyyən bir çoxluqdur və * A üzərində ikili əməliyyatdır, yəni A çoxluğundan olan istənilən iki element a və b üçün a*b elementi də A-ya aiddir. Bu zaman Abel qrupunun aksiomları adlanan aşağıdakı şərtlər yerinə yetirilməlidir:
(i) Assosiativlik: A-dan olan istənilən a, b, c üçün (a*b)*c=a*(b*c) bərabərliyi yerinə yetirilir.
(ii) A-da elə bir e elementi mövcuddur ki, A-dan olan istənilən a üçün a*e=e*a=a bərabərlikləri yerinə yetirilir.
(iii) A-dan olan istənilən a üçün elə bir b elementi mövcuddur ki, a*b=b*a=e bərabərlikləri yerinə yetirilir.
(iv) Kommutativlik: A-dan olan istənilən a, b üçün a*b=b*a bərabərliyi yerinə yetirilir.
Abel qrupunun mühüm bir nümunəsi n tərtibində dövri qrupdur: 0-dan n-1-ə qədər olan ədədlər çoxluğu və n modulu üzrə toplama əməliyyatı. Bu, _n kimi işarə olunur.
İki Abel qrupu G=(A,*) və H=(B,·)-nin birbaşa cəmi G H = (C, ×) cütüdür, burada C={(a,b) : a A, b B} və (a_1, b_1) × (a_2, b_2) = (a_1 * a_2, b_1 · b_2) bütün a_1, a_2 A və b_1, b_2 B üçün.
İki qrup G=(A,*) və H=(B,·) izomorfik adlanır, əgər A-dan B-yə qarşılıqlı təkabül edən bir f təsviri mövcuddur ki, f(a_1)· f(a_2)=f(a_1 * a_2) bütün a_1, a_2 A üçün.
Abel qrupları nəzəriyyəsinin əsas teoremi təsdiq edir ki, istənilən sonlu Abel qrupu bəzi dövri qrupların birbaşa cəminə izomorfikdir.
Çin qalıq teoremi təsdiq edir ki, _mn yalnız və yalnız m və n qarşılıqlı sadə olduqda _m _n-ə izomorfikdir.
Son iki bəyanat n tərtibində izomorfizmə qədər bütün Abel qruplarını təsvir etməyə imkan verir.
Məsələn, əgər n sadədirsə, onda n tərtibində bütün qruplar _n-ə izomorfikdir.
4 tərtibində 2 izomorf olmayan qrup mövcuddur: _4 və _2 _2.
27 tərtibində 3 izomorf olmayan qrup mövcuddur: _27, _9 _3 və _3 _3 _3.
36 tərtibində 4 izomorf olmayan qrup mövcuddur: _4 _9, _2 _2 _9, _4 _3 _3 və _2 _2 _3 _3.
Giriş verilənləri
Giriş faylının ilk sətrində boşluqla ayrılmış təbii ədədlər m ≤ 10^9, N ≤ 200000 və T ≤ 10^5 verilir. Növbəti T sətrin hər birində boşluqla ayrılmış təbii ədədlər L, R ≤ N verilir ki, L ≤ R.
Çıxış verilənləri
Giriş faylındakı hər bir L və R cütü üçün müvafiq cəmin qiymətini ayrıca sətirdə çıxarın.