1222.cpp

来自「求n!的最低位不是0的数.用到数学规律和mod」· C++ 代码 · 共 123 行

/*
一个数的阶乘(除了0和1)肯定是偶数,1*2*3*4*6*7*8*9%10=6
提出5的倍数单独处理,变成5^n*(1*2*3*4*5........)而且2的倍数一定比5的多.
乘5就等于乘10除2,乘10对我们的结果没有影响,考虑除2,记住末尾是偶数;
所以2 / 2 = 6;
    4 / 2 = 2;
    6 / 2 = 8;
    8 / 2 = 4;  
 
1.求n的最低位的数,确定m 
2.求n中包含几个5的倍数:5,10,15,20........n/5;
3.看(n/5)%4为多少(只与n/5的最后2位有关系); 因为m/2只可能是2,4,6,8周期为4的循环
4.再次确定m(根据第3点)
5.一直求到n<10; 
*/
#include<iostream>
#include<cstring>
using namespace std;

int start,len,mm[150];
char n[110];



int main()
{

char ch;
int m,i,last,m4,add,number,nonzero;

while(cin>>n)
{
len = strlen(n);

//cout<<start<<len<<endl;  //add

//nonzero = f(n);
start = 0;
number = 0;
while(len - start > 1)
 { last = n[len - 1] - 48;
          switch(last)
          { case 0:
            case 1:
            case 3:
            case 9: {m = 6;break;}
            case 2: {m = 2;break;}
            case 4:
            case 5:
            case 6:
            case 8: {m = 4;break;}
            case 7: {m = 8;break;}
          }
         if((n[start] - 48) / 5 == 0)
         {
             ch = n[start];
             n[start] = '0';
             start++;
             n[start] += (ch - 48)*10;
         }
		 add = 0;
         for(i = start;i < len;i++)
         {
             ch = (n[i] - 48 + add * 10) / 5 + 48;
             add = (n[i] - 48) % 5;
			 n[i] = ch;
         }
         m4 = (n[len - 2] - 48) * 10 + (n[len - 1] - 48);
         m4 %= 4;
         if(m == 2)
         {switch(m4)
          {case 0: {m = 2;break;}
           case 1: {m = 6;break;}
           case 2: {m = 8;break;}
           case 3: {m = 4;break;}
          }
         } else if(m == 4)
                { switch(m4)
                 {case 0: {m = 4;break;}
                  case 1: {m = 2;break;}
                  case 2: {m = 6;break;}
                  case 3: {m = 8;break;}}
                } else if(m == 6) 
                       { switch(m4)
                         {case 0: {m = 6;break;}
                          case 1: {m = 8;break;}
                          case 2: {m = 4;break;}
                          case 3: {m = 2;break;}}
                       }else {switch(m4)
                               {case 0: {m = 8;break;}
                                case 1: {m = 4;break;}
                                case 2: {m = 2;break;}
                                case 3: {m = 6;break;}}
                             }
  mm[number] = m;
  number++;                           
         
 }
   switch(n[start] - 48)
     {case 0:
      case 1: {mm[number] = 1;break;}
      case 2:
      case 5:
      case 6:
      case 8: {mm[number] = 2;break;}
      case 3: {mm[number] = 6;break;}
      case 4:
      case 7: {mm[number] = 4;break;}
      case 9: {mm[number] = 8;break;}
     }

nonzero = 1;   
for(i = 0;i <= number;i++)
   nonzero = nonzero * mm[i] % 10;

cout<<nonzero<<endl;

}

return 0;
}