题意:
????? 求P(n,m)的最后一位非零数。
?
思路:
????? 讨论1-----n中2,5,3,7,9因子的个数,具体移步
http://duanple.blog.163.com/blog/static/7097176720081016113033592/
?
按照我的理解,求n!最后非零为,先把1----n中‘2’和‘5’的因子的数量求出来,因为只有2和5可以构成0,接下来就要分别求出1---n中最后一位为3,7,9的数字的数量,然后相乘就可以得到n!的最后一位的数
#include<iostream> #include<cstring> #include<cstdio> using namespace std; typedef long long ll; ll n, m; ll get25(ll n ,ll x){ ll res = 0; while(n){ res+=n/x; n/=x; } return res; } ll getodd(int n ,int x){ if(n == 0)return 0; return n/10 + (n%10 >= x) + getodd(n/5 ,x); } ll gao(int n ,int x){ if(n == 0)return 0; return gao(n/2,x)+getodd(n ,x); } int table[4][4] ={ 6,2,4,8,//last digit of 2^4 2 2^2 2^3 1,3,9,7,//...3 1,7,9,3,//...7 1,9,1,9,//...9 }; int main(){ while(cin>>n>>m){ m = n - m; ll two = get25(n ,2) - get25(m ,2); ll five = get25(n ,5) - get25(m ,5); ll three = gao(n ,3) - gao(m ,3); ll seven = gao(n ,7) - gao(m ,7); ll nig = gao(n ,9) - gao(m ,9); // cout<<two<<" "<<five; if(two<five){ puts("5"); continue; } ll res = 1; if(two != five)res *= table[0][(two - five)%4]; res *= table[1][(three)%4]; res *= table[2][(seven)%4]; res *= table[3][(nig)%4]; res %= 10; printf("%I64d\n",res); } return 0; }
?
原文:http://bbezxcy.iteye.com/blog/2164453