[UVa] 10139 - Factovisors

題目網址: http://goo.gl/BNY3Hk

題意: 給兩整數 n, m ( 0 <= n,m <= 2^31-1)，問 n! 是否能被 m 整除。


解法: 質因數分解，比較分解後的每個質數的次方與找出每個質數在 n! 中的個數，是否 m 的每個質數分解出來的次方都小於該質數在 n! 中的個數。

TAG: Prime, Math

注意: 在 n! 中找某質數的次方數方法要注意，否則會TLE

程式碼:

	/**
	* Tittle: 10139 - Factovisors
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/09
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	typedef long long ll;
	// declarations
	ll n, m;
	bool isprime[50005];
	ll prime[25000];
	int pcnt;
	// functions
	int dfact( ll fact, ll div )
	{
	static int cnt;
	static ll tmp;
	cnt = 0;
	tmp = div;
	while( tmp <= fact ) {
	cnt += fact/tmp;
	tmp *= div;
	}
	return cnt;
	}
	bool check( ll a, ll b )
	{
	static ll tmp;
	static int cnt;
	if( b == 0LL ) return false;
	if( b == 1LL ) return true;
	for( int i=1; i<=pcnt && prime[i]*prime[i]<=b; ++i ) if( b%prime[i] == 0 ) {
	cnt = 0;
	while( b%prime[i] == 0 ) {
	b /= prime[i];
	++cnt;
	}
	if( cnt > dfact(a,prime[i]) )
	return false;
	}
	if( b != 1LL && b > a )
	return false;
	return true;
	}
	// main function
	int main( void )
	{
	// init
	pcnt = 0;
	clr( isprime, true );
	isprime[0]=isprime[1]=false;
	for( ll i=2LL; i<=50000LL; ++i ) if( isprime[i] ) {
	prime[++pcnt] = i;
	for( ll j=i*i; j<=50000LL; j+=i )
	isprime[j] = false;
	}
	// input
	while( scanf( "%lld%lld", &n, &m )== 2 ) {
	// output
	if( check(n,m) )
	printf( "%lld divides %lld!\n", m, n );
	else
	printf( "%lld does not divide %lld!\n", m, n );
	}
	return 0;
	}

view raw 10139 - Factovisors.cpp hosted with ❤ by GitHub