Ungkapkan faktorial n sebagai hasil tambah nombor berturut-turut

Kita akan membincangkan dua kaedah untuk mengetahui cara menyatakan pemfaktoran nombor sebagai hasil tambah nombor berturut-turut. Kaedah pertama ialah kaedah langsung dan mudah, manakala dalam kaedah lain kita menggunakan konsep janjang aritmetik untuk menjadikannya kurang kompleks dari segi masa dan ruang yang diduduki.

Pernyataan Masalah

Diberi nombor, kita perlu mencari cara untuk menyatakan pemfaktoran nombor itu sebagai hasil tambah nombor asli yang berturutan.

Ini melibatkan dua fungsi berbeza -

• Cari faktorial bagi suatu nombor.

• Cari bilangan cara nombor boleh dinyatakan sebagai hasil tambah nombor asli berturut-turut.

Contoh 1

Given : Number = 3
Result: 1

Kita semua tahu bahawa faktorial bagi 3 ialah 6, yang boleh ditulis sebagai 1+2+3, jadi jawapan kita ialah: 1 cara.

Contoh 2

Given: Number = 4
Result: 1

Kita semua tahu bahawa faktorial bagi 4 ialah 24, yang boleh ditulis sebagai 7+8+9, jadi jawapan kita ialah: 1 cara.

Kaedah 1

Ini adalah kaedah mudah di mana kita mula-mula mencari faktorial nombor dan kemudian mengira bilangan cara ia boleh dinyatakan sebagai hasil tambah nombor asli berturut-turut. Kaedahnya ialah untuk menyatakan faktorial sebagai satu siri aritmetik panjang len+1 sebagai -

Factorial of Number = p + (p+1) + (p+2) + … + (p+len) 
So, p = (Number- len*(len+1)/2)/(len+1) 
We will check for the values of len from 1 to len*(len+1)/2<Number

Apabila kami mendapat len ​​sebagai integer positif, kami menganggapnya sebagai penyelesaian.

Contoh

Dalam contoh di bawah, kami cuba mencari bilangan cara untuk menyatakan pemfaktoran nombor sebagai hasil tambah nombor berturut-turut.

#include <bits/stdc++.h>
using namespace std;

// code for obtaining number of possible solutions
long int Number_of_solutions(long int NUMBER){
   long int counter = 0;
   for (long int len = 1; len * (len + 1) < 2 * NUMBER; len++) {
      double p = (1.0 * NUMBER - (len * (len + 1)) / 2) / (len + 1);
      if (p - (int)p == 0.0)
      counter++;
   }
   return counter;
}

// main program goes here
int main(){
   long int NUMBER = 15;
   cout << "Number of ways to write 15 as a sum of consecutive numbers: ";
   cout << Number_of_solutions(NUMBER) << endl;
   NUMBER = 10;
   cout << "Number of ways to write 10 as a sum of consecutive numbers: ";
   cout << Number_of_solutions(NUMBER) << endl;
   return 0;
}

Output

Apabila anda menjalankan program C++ di atas, ia akan menghasilkan output berikut -

Number of ways to write 15 as a sum of consecutive numbers: 3 
Number of ways to write 10 as a sum of consecutive numbers: 1

Kaedah 2: Kaedah pengoptimuman

Ini adalah pendekatan yang lebih baik; pendekatan yang kami lihat di atas menyebabkan limpahan.

Jumlah nombor berturut-turut len ​​bermula dari nombor p boleh ditulis sebagai -

sum = (p+1) + (p+2) + (p+3) … + (p+len) 
Hence, sum = (len*(len + 2*p + 1))/2

Sebab sum juga sama dengan Nombor!.

Kita boleh menulis

2*Number! = (len*(len + 2*p + 1))

Di sini, daripada mengira semua pasangan (len, p), kita akan mengira semua pasangan (len, (len + 2*p + 1)). Ini bermakna kita akan mengira semua pf yang dipesan (A, B) dengan AB=2*Nombor! Dan A< B 且 A 和 B 的奇偶性不同，这意味着如果 len 是奇数，则 (len + 2*p + 1) 是偶数，如果 len 是偶数，则 (len + 2*p + 1) 是奇数。

Ini bermakna kami sedang mencari pembahagi ganjil 2*Nombor! Ini juga pembahagi ganjil Nombor!

Kira bilangan pembahagi! , kita perlu mengira kuasa nombor perdana dalam pemfaktoran, bilangan pembahagi ialah (f1 + 1)*(f2 + 1)* … *(fn + 1).

Kami akan menggunakan formula Legendre untuk mengira kuasa tertinggi nombor perdana dalam pemfaktoran nombor.

Contoh

Kod untuk pendekatan ini diberikan di bawah -

#include <bits/stdc++.h>
using namespace std;
#define maximum 5002
vector<int> v;
void sieve(){
   bool Is_the_number_prime[maximum];
   memset (Is_the_number_prime, true, sizeof(Is_the_number_prime) );
   for (int prime = 2; prime * prime < maximum; prime++) {
      if (Is_the_number_prime[prime] == true) {
         for (int iterator = prime * 2; iterator < maximum; iterator += prime)
         Is_the_number_prime[iterator] = false;
      }
   }
   for (int prime = 2; prime < maximum; prime++)
   if (Is_the_number_prime[prime])
   v.push_back(prime);
}
long long int calculate_largest_power(long long int a, long long int b){
   long long int c = 0;
   long long int x = b;
   while (a >= x) {
      c += (a / x);
      x *= b;
   }
   return c;
}
long long int modular_mult(long long int a,
long long int b,
long long int m){
   long long int result = 0;
   a = a % m;
   while (b > 0) {
      if (b % 2 == 1)
      result = (result + a) % m;
      a = (a * 2) % m;
      b /= 2;
   }
   return result % m;
}
long long int no_of_ways(long long int n,
long long int m){
   long long int answer = 1;
   for (int iterator = 1; iterator < v.size(); iterator++) {
      long long int powers = calculate_largest_power(n, v[iterator]);
      if (powers == 0)
      break;
      answer = modular_mult(answer, powers + 1, m)%m;
   }
   if (((answer - 1) % m) < 0)
   return (answer - 1 + m) ;
   else
   return (answer - 1) ;
}
int main(){
   sieve();
   long long int n = 4, m = 7;
   cout << "Number of solutions after performing modulo with 7 is " <<no_of_ways(n, m);
   return 0;
}

Output

Apabila program C++ di atas dijalankan, ia akan menghasilkan output berikut -

Number of solutions after performing modulo with 7 is 1.

Kesimpulan

Dalam artikel ini, kami membincangkan dua cara berbeza untuk mengetahui faktorial nombor sebagai hasil tambah nombor asli berturut-turut.

Atas ialah kandungan terperinci Ungkapkan faktorial n sebagai hasil tambah nombor berturut-turut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!