Przechowywanie dużych liczb - silnia z 21+

Mam problem z przechowywaniem w zmiennych dużych liczb takich jak silnia z 21 oraz wyżej. W jaki sposób mogę przechowywać tak duże liczby?

http://stackoverflow.com/questions/4798777/is-there-a-c-equivalent-to-javas-bigdecimal
https://gmplib.org/

jezeli spoj, to patrz na dwie ostatnie liczby, nie potrzebujesz przechowywac niczego

Jeśli chcesz dwie ostatnie cyfry silnii dowolnej liczby naturalnej to nawet nie trzeba nic mnożyć. Silnia dowolnej liczby dwucyfrowej lub większej kończy się co najmniej dwoma zerami, więc zostaje zrobienie switcha dla silnii liczb jednocyfrowych.

Jeśli chcesz mieć X ostatnich niezerowych cyfr to będzie trudniej, ale dalej prosto jeżeli X jest wystarczająco małe by pow(10, 2 * X) zmieściło się w int32 (czy tam int64). Po prostu po każdym mnożeniu rób modulo pow(10, X).

Hint:
Jeżeli X jest zmienne w małym zakresie to zamiast robić modulo zmienna (tzn a % x_power) możesz zrobić coś takiego:

switch (x) {
  case 0:
    return 0;
  case 1:
    return a % 10;
  case 2:
    return a % 100;
  ...
  case 5:
    return a % 100000;
  default:
    boom();
}

Działanie modulo stała kompilator jest w stanie zamienić na szybkie mnożenia w czasie kompilacji.

No właśnie SPOJ, np. te zadanie: http://pl.spoj.com/problems/FCTRL3/ Muszę najpierw obliczyć silnię, a potem wypisać liczbę jedności i dziesiątek, a muszę mieć do tego całą liczbę w pamięci.

Lub to: http://pl.spoj.com/problems/PA05_POT/
Też muszę mieć najpierw wynik potęgowania by potem wypisać rozwiązanie.

Nie musisz. Zarówno potęgowanie jak i liczenie silni opiera się na mnożeniu. Mnożenie liczb całkowitych ma to do siebie, że tylko ostatnie X cyfr każdego z czynników ma wpływ na ostatnie X cyfr iloczynu.

W obu tych zadaniach nie trzeba liczyc ani silnii, ani potegi.

a muszę mieć do tego całą liczbę w pamięci.
A gdzie tak jest napisane? W zadaniu nie ma takiego przykazu.

Merhaba napisał(a):

No właśnie SPOJ, np. te zadanie: http://pl.spoj.com/problems/FCTRL3/ Muszę najpierw obliczyć silnię ...

Gó...zik prawda, nawet dodawać (nie mówiąc o mnożeniu) nie trzeba, wystarczy pomyśleć:

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

int main()
  {
   const char *tb[]={"","0 1","0 2","0 6","2 4","2 0","2 0","4 0","2 0","8 0","0 0"};
   unsigned t,v=0;
   for(cin>>t;t--;cout<<tb[max(1U,min(10U,v))]<<endl) cin>>v;
   return 0;
  }

Zepsuję zabawę :P

Silnia (bez wpisanych na sztywno tablic):

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
 
int main(int argc, char** argv) {
    int32_t d, n, x;
    scanf("%d", &d);
    while (d--) {
        scanf("%d", &n);
        for(x = 1; n && (x %= 100); x *= n--);
        printf("%d %d\n", x / 10, x % 10);
    }
    return EXIT_SUCCESS;
}

Potęga:

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(int argc, char** argv) {
    int32_t d, a, b, x, t[20], u[20], i, p;
    scanf("%d", &d);
    while (d--) {
        scanf("%d %d", &a, &b);
        a %= 10;
        memset(t, 0, sizeof(t));
        for (i = 0, x = 1; !t[u[i] = x %= 10]; t[x] = ++i, x *= a);
        p = i - t[x] + 1;
        printf("%d\n", u[!b || b % p ? b % p : p]);
    }
    return EXIT_SUCCESS;
}