Factovisors

Factovisors

时间： 1ms        内存：64M

描述：

The factorial function, n! is defined as follows for all non-negative integers n:

0! = 1
n! = n x (n - 1)! (n > 0)

We say that a divides b if there exists an integer k such that

k x a = b

输入：

The input to your program consists of several lines, each containing two non-negative integers, n and m, both less than 2³¹.

输出：

For each input line, output a line stating whether or not m divides n!, in the format shown below.

示例输入：

6 9
6 27
20 10000
20 100000
1000 1009

示例输出：

9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!

提示：

参考答案（内存最优[1788]）：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
long LEN = 1 << 16;
vector<long> primes;
void init()
{
    bool filter[LEN];
    for ( int i=0; i<LEN; i++ ) filter[i] = true;
    long max = (long)sqrt(LEN)+1;
    for ( int i=2; i<=max; i++ )
        if ( filter[i] )
            for ( int j=2*i; j<LEN; j+=i )
                filter[j] = false;
    for ( int i=2; i<LEN; i++ )
        if ( filter[i] )
            primes.push_back(i);
}
bool divByP2Kth(long p, long k, long n)
{
    if ( k==0 ) return true;
    long cnt = 0;
    for ( long i=p; i<=n; i*=p )
    {
        cnt += n/i;
        if ( cnt >= k ) return true;
    }
    return false;
}
bool divide(long m, long n)
{
    if ( m==0 )return false;
    else if (m==1)return true;
    for (unsigned int i=0; i<primes.size(); i++ )
    {
        long p =primes.at(i), k = 0;
        while ( m%p == 0 )
        {
            k++;
            m /= p;
        }
        if ( ! divByP2Kth(p,k,n) ) return false;
        if ( m==1 ) break;
    }
    if ( m>1 && ! divByP2Kth(m,1,n) ) return false;
    return true;
}
int main()
{
    init();
    long n, M;
    while (cin >> n >> M)
    {
        bool ok = divide(M,n);
        if (ok)cout << M << " divides " << n << "!" << endl;
        else cout << M << " does not divide " << n << "!" << endl;
    }
    return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
long LEN = 1 << 16;
vector<long> primes;
void init()
{
    bool filter[LEN];
    for ( int i=0; i<LEN; i++ ) filter[i] = true;
    long max = (long)sqrt(LEN)+1;
    for ( int i=2; i<=max; i++ )
        if ( filter[i] )
            for ( int j=2*i; j<LEN; j+=i )
                filter[j] = false;
    for ( int i=2; i<LEN; i++ )
        if ( filter[i] )
            primes.push_back(i);
}
bool divByP2Kth(long p, long k, long n)
{
    if ( k==0 ) return true;
    long cnt = 0;
    for ( long i=p; i<=n; i*=p )
    {
        cnt += n/i;
        if ( cnt >= k ) return true;
    }
    return false;
}
bool divide(long m, long n)
{
    if ( m==0 )return false;
    else if (m==1)return true;
    for (unsigned int i=0; i<primes.size(); i++ )
    {
        long p =primes.at(i), k = 0;
        while ( m%p == 0 )
        {
            k++;
            m /= p;
        }
        if ( ! divByP2Kth(p,k,n) ) return false;
        if ( m==1 ) break;
    }
    if ( m>1 && ! divByP2Kth(m,1,n) ) return false;
    return true;
}
int main()
{
    init();
    long n, M;
    while (cin >> n >> M)
    {
        bool ok = divide(M,n);
        if (ok)cout << M << " divides " << n << "!" << endl;
        else cout << M << " does not divide " << n << "!" << endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。