将阶乘n表示为连续数字的和

我们将讨论两种方法来找出如何将数字的阶乘表示为连续数字的总和。第一种方法是直接而简单的方法，而在另一种方法中，我们使用算术级数的概念来使其在占用的时间和空间方面不那么复杂。

问题陈述

给定一个数字，我们需要找出可以将数字的阶乘表示为连续自然数之和的方法。

这涉及两个不同的功能 -

• 求数字的阶乘。

• 找出可以将数字表示为连续自然数之和的方法数。

示例1

Given : Number = 3
Result: 1

众所周知，3 的阶乘是 6，可以写成 1+2+3，因此我们的答案是：1 种方式。

示例2

Given: Number = 4
Result: 1

众所周知，4 的阶乘是 24，可以写成 7+8+9，因此我们的答案是：1 种方式。

方法 1

这是一种简单的方法，我们首先找出数字的阶乘，然后计算可以将其表示为连续自然数之和的方法数。该方法是将阶乘表示为算术长度 len+1 的级数为 -

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

当我们获得 len 为正整数时，我们将其视为一个解。

示例

在下面的示例中，我们尝试找出将数字的阶乘表示为连续数字之和的方法的数量。

#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;
}

输出

当您运行上述 C++ 程序时，它将产生以下输出 -

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

方法2：优化方法

这是一个更好的方法；我们上面看到的方法会导致溢出。

从数字 p 开始的 len 个连续数字的总和可以写为 -

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

因为 sum 也等于 Number!。

我们可以写

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

这里，我们将计算所有 (len, (len + 2*p + 1)) 对，而不是计算所有 (len, p) 对。这意味着我们将计算所有有序的 pf (A, B)，其中 AB=2*Number！并且 A< B 且 A 和 B 的奇偶性不同，这意味着如果 len 是奇数，则 (len + 2*p + 1) 是偶数，如果 len 是偶数，则 (len + 2*p + 1) 是奇数。

这意味着我们正在寻找 2*Number 的奇数约数！这也是 Number 的奇数除数！

要计算除数的数量！，我们必须计算素数在因式分解中的幂，除数的数量为 (f1 + 1)*(f2 + 1)* … *(fn + 1)。

我们将使用勒让德公式计算素数在数字阶乘中的最大幂。

示例

下面给出了这种方法的代码 -

#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;
}

输出

当运行上面的C++程序时，它将产生以下输出 -

Number of solutions after performing modulo with 7 is 1.

结论

在本文中，我们讨论了两种不同的方法来找出数字，将数字的阶乘表示为连续自然数之和。

以上是将阶乘n表示为连续数字的和的详细内容。更多信息请关注PHP中文网其他相关文章！