1570: Cow Brainiacs 

Time Limit(Common/Java):1000MS/10000MS     Memory Limit:65536KByte

Total Submit: 15            Accepted:8

Description

 

One afternoon as the cows were chewing their cud, Bessie said, "Let's have a contest to see who is the smartest cow. Here's the contest: we will choose a positive number N (no larger than 2,000,000) and whoever computes the rightmost non-zero digit of N factorial will be crowned the smartest cow."

The other cows demurred, however, mooing, "We did that last year."

"Oh," said Bessie, "but there's a catch. We're not necessarily going to use base 10. I know my hooves don't have that many digits! We'll just specify a positive number base B from 2 through 30."

Write a program to help the cows judge their intelligence contest.

 

Input

A single line with integers N and B

Output

A single line with the decimal-representation of the "digit" that is the rightmost non-zero digit for N! in base B. If B > 10, go ahead and output a two-digit decimal number as a representation of the final "digit".

Sample Input

 

Sample Output

 

Hint

13*12*11*10*9*8*7*6*5*4*3*2*1=6227020800 base 10, which in base 3 is 121001222020102200000, so the right-most non-zero digit is 2.

求n！的k进制下最后一个非0位的数字，我只想喊666

10进制主要有两种，线性模方程的，之后找到考虑hashtable的

这个竟然就是直接暴力的

#include
        
         int main(){    int n,b,f=1;    scanf("%d%d",&n,&b);    for(int i=2;i<=n;i++)    {        f*=i;        while(f%b==0)            f/=b;        f%=b;    }    printf("%d",f);    return 0;}