Guest User

Untitled

a guest
Jul 22nd, 2012
1,350
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. //Calculating last non-zero digit in n!
  2. //Complexity O(logn)
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. int powmod(int a, int n, int mod)
  8. {
  9.     int res(1);
  10.     while (n)
  11.     {
  12.         if (n&1)
  13.             res=(res*a)%mod;
  14.         a=(a*1ll*a)%mod;
  15.         n>>=1;
  16.     }
  17.     return res;
  18. }
  19.  
  20. int mod5(int n)
  21. {
  22.     if (n==0)
  23.         return 1;
  24.     int res(mod5(n/5));
  25.     if ((n/5)&1)
  26.         res=(res*4)%5;
  27.     for (int i=1; i<=n%5; i++)
  28.         if (i%5!=0)
  29.             res=(res*i)%5;
  30.     return res;
  31. }
  32.  
  33. int deg(int n, int p)
  34. {
  35.     int res(0);
  36.     while (n>=p)
  37.         res+=n/p,n/=p;
  38.     return res;
  39. }
  40.  
  41. int main()
  42. {
  43.     int n;
  44.     scanf("%d",&n);
  45.     int pw2(deg(n,2)),pw5(deg(n,5));
  46.     int m2(powmod(5,pw5,2)%2);
  47.     int m5((mod5(n)*powmod(3,pw2,5))%5);
  48.     int m10(0);
  49.     while ((m10%2!=m2) || (m10%5!=m5))
  50.         ++m10;
  51.     int res((m10*powmod(2,pw2-pw5,10))%10);
  52.     printf("%d\n",res);
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment