Факториал, десятки и единицы

Question

Привет, ребята, я пытаюсь написать программу, которая будет вычислять факториал пройденного номера и показывать его количество десятков и единиц. Это упражнение происходит от spoj.com, но, по-видимому, мой код слишком медленный, и компилятор spoj говорит, что я превысил предел времени.:/Любые идеи о том, как ускорить этот код? :) Я добавил несколько комментариев, пытаясь упростить вам понимание моего кода. #ОБНОВИТЬ. Я реорганизовал свой код и он работает также хорошо, но гораздо короче;)

#include <iostream> 
#include <cmath> 
using namespace std; 

int tests, number, result = 1, units, tens, auxiliary; 

//PROGRAM IS CALCULATING FACTORIAL AND WRITING OUT THE NUMBER OF TENS AND UNITS 
int main() 
{ 
cin >> tests; // number of integers you want to check, for example if you cin >> 5 then you have 5 numbers to check the answer 
for (int i = 0; i < tests;i++) // imputation of integers to tables 
{ 
    cin >> number; 
    result = 1; 
    auxiliary = number; 
    for(int i=0;i<auxiliary;i++) 
    { 
     result = result * number; 
     number -= 1; 
    } 
    units = result % 10; // here I calculate units 
    tens = result % 100; // here I calculate number of tens 
    tens = (tens - units)/10; // here I calculate number of tens #2 
    cout << tens <<" "<< units << endl; // here I write out the answer which has the form "x y" <---- "tens units" 
    tens = 0; 
    units = 0; 

} 
    return 0; 
} 

Answer 1

Вот первые 20 факториалов:

1 
1 
2 
6 
24 
120 
720 
5040 
40320 
362880 
3628800 
39916800 
479001600 
6227020800 
87178291200 
1307674368000 
20922789888000 
355687428096000 
6402373705728000 
121645100408832000 
2432902008176640000 

, Вам не нужно вычислить факториал для любого числа больше чем 10, потому что ваш ответ всегда равен 0, 0. А для остальных 10 вы можете просто распечатать результаты из массива.

Answer 2

На данный момент предположим, что вы хотите на самом деле рассчитать значимый результат, а не просто предварительно вычислить несколько результатов, которые меняются, и сохранить единственный фиксированный результат для всех других входов.

Если вы делаете расчет, вы имеете дело с модульной арифметикой. То есть вы делаете A * B * C ... mod M, для некоторого набора (целочисленных) входов. Что мы можем наблюдать об этом, так это то, что модульная часть этого объекта может быть распределяемой. Например, если какой-либо из входов может быть больше, чем наш модуль (M), мы можем изменить:

A * B mod M 

в:

((A mod M) * (B mod M) mod M) 

... и до сих пор получить тот же результат. Мы также можем сделать то же самое со всеми нашими промежуточными результатами, так что для некоторого произвольного числа входов:

A * B * C * D * E [...] mod M 

может стать:

intermediate = A mod M; 
for (V in A, B, D, E [...]) 
    intermediate *= V mod M; 
    intermediate = intermediate mod M; 

... и до сих пор получить тот же результат.

Это означает, что наибольшее число, с которым мы когда-либо имели дело, составляет приблизительно M . В вашем случае M = 100, поэтому нам не нужно представлять число, большее 10000. Это означает, что он всегда будет вписываться в int (так как он будет поддерживать не менее 16-разрядных номеров.

Использование модульных Таким образом, мы можем сделать умножение намного. Более интересно, что эта базовая техника распространяется на довольно много интересных случаев, чем только эта (например, она используется на регулярной основе при внедрении RSA-шифрования/дешифрования).