Given two numbers A and B. The task is to compute the last digit of the resulting F, where F= B! / A! .
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains two number A and B as input.
Output:
For each test case, print last digit of B! / A! (B factorial/ A factorial).
Constraints:
1<=T<=100
1<=A<=B<=1018
Example:
Input:
2
2 4
107 109
Output:
2
2
Explanation:
Input : A = , B = Output : Explanation : A! = and B! = . F = / = --> last digit =
解题思路:
B!/A!=B*(B-1)*...*(A+1)即只需要求出B*(B-1)*...*(A+1)的最后一位即可
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 ...
会发现只要A、B两个数字相差>4,那么他们最后一位一定是0
当A、B两个数字相差<4时,只需要循环求出B*(B-1)*...*(A+1)的最后一位数字即可。但是因为AB都是在1-10^18,所以我们只需要求这个式子中每一个数字的最后一位相乘的乘积即可。
#include <stdio.h> #include <stdlib.h> int main() { int num,i,j; scanf("%d",&num); long long *Arr=(long long *)malloc(sizeof(long long)*2*num); int *Brr=(int *)malloc(sizeof(int)*num);//存放结果 for(i=0;i<2*num;i++)//输入各个A、B { scanf("%d",&Arr[i]); } for(i=0;i<num;i++)//对每一个用例进行处理 { for(j=0;j<2*num;j=j+2) { if(Arr[j+1]-Arr[j]>4)//相差大于4,则最后一位一定是0 { Brr[i]=0; } else//相差小于等于4,则只需要(B*(B-1)*....*(A+1))其中只需要计算最后一位相乘的即可。 { int mul=1,k; for(k=Arr[j+1];k>Arr[j];k--)//一共有(Arr[2*i+1]-Arr[2*i])个数相乘 { mul=mul*(Arr[k]%10); } Brr[i]=mul%10; } } } for(i=0;i<num;i++) printf("%d\n",Brr[i]); return 0; }