TOJ 假题之 Cow Brainiacs

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<stdio.h>
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;
}