http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2352好久沒有做數(shù)論題了，弱死了，這題弄了N久，因?yàn)闆]有考慮0這個特殊的家伙不能作為除數(shù)。
題意相當(dāng)簡單，就是判斷m能否整除n！。
解法：對m進(jìn)行素因數(shù)分解，m = p1^t1 * p2^t2 * ... * ps^ts。那么對于pi，判斷n！是否含有x個因數(shù)，使得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>
9using namespace std;
10typedef __int64 ll;
11
12const int maxn = 66000;
13bool vis[ maxn ];
14ll p[ maxn ];
15int plen, flen;
16int a[ 65 ], b[ 65 ];
17
18void 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
33void num_factor( ll n ) //在有素?cái)?shù)表的前提下的素因數(shù)分解
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
48int 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
59int 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