http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2352好久没有做数论题了,弱死了,这题弄了N久,因为没有考虑0这个特殊的家伙不能作为除数。
题意相当简单,就是判断m能否整除n!。
解法:对m进行素因数分解,m = p1^t1 * p2^t2 * ... * ps^ts。那么对于pi,判断n!是否含有x个因数,使得x >= ti。

tzc_2352
1
#include <cstdio>
2
#include <iostream>
3
#include <cmath>
4
#include <algorithm>
5
#include <cstring>
6
#include <string>
7
#include <complex>
8
#include <queue>
9
using namespace std;
10
typedef __int64 ll;
11
12
const int maxn = 66000;
13
bool vis[ maxn ];
14
ll p[ maxn ];
15
int plen, flen;
16
int a[ 65 ], b[ 65 ];
17
18
void prime( )
19

{
20
ll i, j, k;
21
plen = 0;
22
memset( vis, false, sizeof( vis ) );
23
for( i = 2, k = 4; i < maxn; ++i, k += i + i - 1 )
24
{
25
if( !vis[i] )
26
{
27
p[ plen++ ] = i;
28
if( k < maxn ) for( j = k; j < maxn; j += i ) vis[ j ] = true;
29
}
30
}
31
}
32
33
void num_factor( ll n ) //在有素数表的前提下的素因数分解
34

{
35
int i;
36
flen = 0;
37
for( i = 0; p[ i ] * p[ i ] <= n; i++ )
38
{
39
if( n % p[ i ] == 0 )
40
{
41
for( b[ flen ] = 0; n % p[ i ] == 0; ++b[ flen ], n /= p[ i ] );
42
a[ flen++ ] = p[ i ];
43
}
44
}
45
if( n > 1 ) b[ flen ] = 1, a[ flen++ ] = n;
46
}
47
48
int factor( ll n, ll p )
49

{
50
int sum = 0;
51
while( n )
52
{
53
n /= p;
54
sum += n;
55
}
56
return sum;
57
}
58
59
int main(int argc, char *argv[])
60

{
61
ll n, m;
62
prime( );
63
while( scanf("%I64d %I64d",&n,&m) != EOF )
64
{
65
if( m == 0 )
66
{
67
printf("0 does not divide %I64d!\n",n);
68
continue;
69
}
70
num_factor( m );
71
int flag = 0;
72
for( int i = 0; i < flen; i++ )
73
{
74
int tmp = factor( n, a[ i ] );
75
if( tmp < b[ i ] )
{ flag = 1; break; }
76
}
77
if( flag ) printf("%I64d does not divide %I64d!\n",m,n);
78
else printf("%I64d divides %I64d!\n",m,n);
79
}
80
return 0;
81
}
82