我們將討論兩種方法來找出如何將數字的階乘表示為連續數字的總和。第一種方法是直接而簡單的方法，而在另一種方法中，我們使用算術級數的概念來使其在佔用的時間和空間方面不那麼複雜。
問題陳述
給定一個數字，我們需要找出可以將數字的階乘表示為連續自然數總和的方法。
這涉及兩個不同的功能 -
求數字的階乘。
找出可以將數字表示為連續自然數總和的方法數。
範例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中文網其他相關文章！
