Pagini recente » Cod sursa (job #2790063) | Cod sursa (job #828120) | Cod sursa (job #1514116) | Cod sursa (job #1613030) | Cod sursa (job #603330)
Cod sursa(job #603330)
#include <iostream>
#include <fstream>
using namespace std;
int Factorial[100000], N, Pow[100000];
void Multiply (int A[], int B[], int S[])
{
int i, j, k, Aux[100000], P[100000];
for (i=0; i<=A[0]+B[0]; ++i)
{
P[i]=0;
}
for (i=A[0]; i>0; --i)
{
k=1;
for (j=B[0]; j>0; --j)
{
P[k+A[0]-i]+=(A[i]*B[j]);
if (P[k+A[0]-i]>99)
{
P[k+A[0]+1-i]+=(P[k+A[0]-i]/100);
P[k+A[0]-i]%=100;
}
++k;
}
}
i=A[0]+B[0];
while (P[i]==0)
{
--i;
}
P[0]=i;
for (i=1; i<=P[0]; ++i)
{
if (P[i]>99)
{
if (P[i+1]==0)
{
++P[0];
}
P[i+1]+=(P[i]/100);
P[i]%=100;
}
}
for (i=P[0]; i>0; --i)
{
Aux[P[0]-i+1]=P[i];
}
S[0]=P[0];
for (i=1; i<=P[0]; ++i)
{
S[i]=Aux[i];
}
}
void HugePower (int N[], int P, int S[])
{
int M[100000];
S[0]=1;
S[1]=1;
for (; P; P/=2)
{
if (P%2==1)
{
Multiply (S, N, M);
for (int i=1; i<=M[0]; ++i)
{
S[i]=M[i];
}
S[0]=M[0];
}
Multiply (N, N, M);
for (int i=1; i<=M[0]; ++i)
{
N[i]=M[i];
}
N[0]=M[0];
}
}
int main ()
{
//ifstream fin ("patrate2.in");
//ofstream fout ("patrate2.out");
freopen ("patrate2.in", "r", stdin);
freopen ("patrate2.out", "w", stdout);
int n[100000];
Factorial[0]=1;
Factorial[1]=1;
//fin >> N;
scanf ("%d", &N);
for (int i=1; i<=N; ++i)
{
n[0]=0;
for (int j=i; j>0; j/=100)
{
++n[0];
}
int k=n[0];
for (int j=i; j>0; j/=100, --k)
{
n[k]=j%100;
}
Multiply (Factorial, n, Factorial);
}
n[0]=1;
n[1]=2;
HugePower (n, N*N, Pow);
Multiply (Factorial, Pow, Factorial);
for (int i=1; i<=Factorial[0]; ++i)
{
if (Factorial[i]<10 && i!=1)
{
printf ("0");
}
printf ("%d", Factorial[i]);
}
printf ("\n");
//fin.close ();
//fout.close ();
return 0;
}