[USACO 2002 Orange] Cow Brainiacs

_鱼非仙_ · 2020-08-09 18:47:15 · 个人记录

原题

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 29."

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

PROBLEM NAME: brain

INPUT FORMAT:

A single line with integers N and B

SAMPLE INPUT (file brain.in):

13 3

OUTPUT FORMAT:

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 OUTPUT (file brain.out):

2

[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! 在 m 进制下最后一位的非零数。

思路

n! 在 m 进制下末尾的零一定是多个 m 的乘积，而 m 又是由 m 的质因子乘出来的。因此可以预处理 m 的所有质因子，然后 i 从 2 到 n 累乘，每次把 i 的所有 和 m 的质因子相同 的质因子提取出来，这样可以保证乘出来的结果在 m 进制下末尾没有零。

接下来处理剩下的那些数（刚刚提取出来的数），对于 m 的所有质因子 p 及其指数 k，还有剩下数以 p 为底的指数 l，令

z \gets \min \lfloor \frac{l}{k} \rfloor

则 z 就是 n! 在 m 进制下末尾零的个数，除去它们（p^{z \times k}），再剩下的数（p^{l-z \times k}）与原来的数累乘，结果对 m 取模，即可得到答案。

代码

#include <iostream>
#include <cstdio>

const int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

int n, m;
int ps[10];
int sum(1);
int nps[10];

inline int pow(int x, int y, int p = m)
{
    int ret(1);
    while (y)
    {
        if (y & 1)
            ret = ret * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ret;
}

int main()
{
    scanf("%d%d", &n, &m);
    int foo(m);
    for (int i = 0; i < 10; ++i)
    {
        while (foo % prime[i] == 0)
        {
            foo /= prime[i];
            ++ps[i];
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        foo = i;
        for (int j = 0; j < 10; ++j)
        {
            if (!ps[j])
                continue;
            while (foo % prime[j] == 0)
            {
                foo /= prime[j];
                ++nps[j];
            }
        }
        sum = sum * foo % m;
    }
    foo = 0x3F3F3F3F;
    for (int i = 0; i < 10; ++i)
    {
        if (!ps[i])
            continue;
        int bar(nps[i] / ps[i]);
        if (bar < foo)
            foo = bar;
    }
    int bar = 1;
    for (int i = 0; i < 10; ++i)
    {
        bar = bar * pow(prime[i], (nps[i] - ps[i] * foo)) % m;
    }
    printf("%d\n", sum * bar % m);
    return 0;
}