The Last Non-zero Digit(POJ - 1150)(计数好题)

前言

很难想

题目

Vjudge
POJ
题目大意
给定 $N,M$ $（0\le M\le N\le 20000000）$，计算$A_m^n$的最低非0位

思路

我们知道 $A_n^m=\frac{n!}{(n?m)!}$
同时 $10=2?5$
也就是计算 $n?m+1$ ~ $n$ 非0末位乘积的非0末位
那么我们知道从个位数判断2,5需要数字:2,4,5,6,8（没有0）
我们记 $getnu{m}_2(n)$ 为 $n!$中 2倍数 的个数(去0)
我们记 $getnu{m}_5(n)$ 为 $n!$中 5 的个数(去0)
那么：
$getnu{m}_2(n)=n/2+getnu{m}_2(n/2)$
$getnu{m}_5(n)=n/5+getnu{m}_5(n/5)$
我们可以这样理解：
$1?2?3?4?5?6?7?8?9?10.....$
其中2的倍数为，个数为 $n/2$
$2?4?6?8?10.....$
整体除以2后又是原来的样子，只不过数量减半
5同理
那我们只需要处理 3,7,9 了
我们记 $f(n,x)$ 为 $n!$ 中 各个数字末位为 $x$倍数 的个数(去0)
我们再来看看
$1?2?3?4?5?6?7?8?9?10.....$
其实偶数由于处理了2所以全部变成了：
$1?1?3?1?5?3?7?1?9?5?1?3?3?7.....$
就可以除以2变为 $f(n/2,x)$
那么奇数我们可以单独写一个函数来处理：
$g(n,x)$:n!中奇数位出现x的次数
那么 $g(n,x)=n/10+(n\%10>=x)+g(n/5,x)$
我们再来看看
$1?3?5?7?9?11?13?15.....$
那么由于处理了5所以变成了
$1?3?1?7?9?11?13?3.....$
那么 $f(n,x)=f(n/2,x)+g(n,x)$
在注意一下，如果$num2>=num5$要特殊处理

#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
#define MAXN 10
#define INF 0x3f3f3f3f
int table[4][4]={
    //2,3,7,9
{
    6,2,4,8},
{
    1,3,9,7},
{
    1,7,9,3},
{
    1,9,1,9}
};
int get2(int n){
    if(n==0) return 0;return n/2+get2(n/2);
}
int get5(int n){
    if(n==0) return 0;return n/5+get5(n/5);
}
int getnum(int n,int x){
    //3,7,9if(n==0) return 0;return n/10+(n%10>=x)+getnum(n/5,x);
}
int cal(int n,int x){
    if(n==0) return 0;return cal(n/2,x)+getnum(n,x);
}
int main(){
    int n,m;while(~scanf("%d %d",&n,&m)){
    m=n-m;int ans=1;int num2=get2(n)-get2(m);int num5=get5(n)-get5(m);int num3=cal(n,3)-cal(m,3);int num7=cal(n,7)-cal(m,7);int num9=cal(n,9)-cal(m,9);//printf("%d %d %d %d %d\n",num2,num5,num3,num7,num9);if(num5>num2){
    puts("5");continue;}if(num2>num5)ans*=table[0][(num2-num5)%4],ans%=10;ans*=table[1][num3%4],ans%=10;ans*=table[2][num7%4],ans%=10;ans*=table[3][num9%4],ans%=10;printf("%d\n",ans);}return 0;
}