http://acm.fzu.edu.cn/problem.php?pid=19712010年福州网赛A题，AC出的身体，看了AC的解题报告写的，死活不会那个证明，然后就用了第二种方法。题解详见： http://hi.baidu.com/aekdycoin/blog/item/e87f5f9653423c6255fb969b.html Orz AekdyCoin PS: 题目有个邪恶的地方，N是正数，而最后的Ans是 0到M-1 的。
  fzu 1971
1/**//*
2 I believe in AekdyCoin
3 */
4 #include <cstdio>
5#include <iostream>
6#include <complex>
7#include <algorithm>
8#include <cmath>
9#include <cstring>
10using namespace std;
11typedef __int64 ll;
12
13const int maxn = 33;
14const int maxm = 32010;
15
16bool vis[ maxm ];
17ll pp[ maxm ];
18int plen, flen, cnt;
19
20ll aa[ 65 ], bb[ 65 ];
21ll buf[ 100000 ];
22
23void prime( )
24 {
25 ll i, j, k;
26 plen = 0;
27 memset( vis, false, sizeof( vis ) );
28 for( i = 2, k = 4; i < maxm; ++i, k += i + i - 1 )
29  {
30 if( !vis[ i ] )
31 {
32 pp[ plen++ ] = i;
33 if( k < maxm ) for( j = k; j < maxm; j += i ) vis[ j ] = true;
34 }
35 }
36}
37
38void num_factor( ll n ) //在有素数表的前提下的素因数分解
39{
40 int i;
41 flen = 0;
42 for( i = 0; pp[ i ] * pp[ i ] <= n; i++ )
43 {
44 if( n % pp[ i ] == 0 )
45 {
46 for( bb[ flen ] = 0; n % pp[ flen ] == 0; ++bb[ flen ], n /= pp[ i ] );
47 aa[ flen++ ] = pp[ i ];
48 }
49 }
50 if( n > 1 ) bb[ flen ] = 1, aa[ flen++ ] = n;
51}
52
53ll mod( ll a, ll mod ){ return ( a % mod + mod ) % mod; }
54
55ll pow_mod( ll a, ll b, ll mod )
56{
57 ll ans = 1, d = a % mod;
58 while( b )
59 {
60 if( b & 1 ) ans = ans * d % mod;
61 d = d * d % mod;
62 b >>= 1;
63 }
64 return ans;
65}
66
67void ex_gcd( ll a, ll b, ll & d, ll & x, ll & y )
68{
69 if( !b ) { d = a, x = 1, y = 0; }
70 else
71 {
72 ex_gcd( b, a % b, d, y, x );
73 y -= x * ( a / b );
74 }
75}
76
77ll china ( ll a[ ], ll m[ ], ll n ) // X mod m[i]=a[i] ，求解 X ,m[i]两两互素
78{
79 ll M = 1, d, y, x, X;
80 for( int i = 0; i < n; i++ )
81 M = M * m[ i ];
82 X = 0;
83 for( int i = 0; i < n; i++ )
84 {
85 ll w = M / m[ i ];
86 ex_gcd( m[ i ], w, d, x, y ); // don 't care about others
87 X = ( X + y * w * a[ i ] ) % M; // accumulate e*的和a
88 }
89 return mod( X, M ) ? mod( X, M ) : M; // adjust to [0,M-1]
90}
91
92// A = 52 mod = 8 A % 2 == 0 ans = 2^(c-1)
93// A = 53 mod = 0 ans = 0
94
95ll b[ maxn ], p[ maxn ], c[ maxn ], g[ maxn ], PC[ maxn ];
96ll B[ maxn ];
97ll K, A, N, M, ans;
98
99void DFS( int dep, ll tem )
100{
101 int i;
102 if( dep == flen )
103 {
104 buf[ cnt++ ] = tem;
105 return;
106 }
107 ll temp = 1;
108 for( i = 0; i <= bb[ dep ]; i++ )
109 {
110 DFS( dep + 1, tem * temp );
111 temp *= aa[ dep ];
112 }
113}
114
115void find_g( ) // 暴力找原根
116{
117 for( int j = 0; j <= K; j++ )
118 {
119 if( p[ j ] == 2 ) continue;
120 ll phi = PC[ j ] / p[ j ] * ( p[ j ] - 1 );
121 cnt = 0;
122 num_factor( phi );
123 DFS( 0, 1 );
124 for( int i = 2; ; i++ )
125 {
126 int k;
127 for( k = 0; k < cnt; k++ )
128 {
129 if( buf[ k ] != phi && pow_mod( i, buf[ k ], PC[ j ] ) == 1 )
130 break;
131 }
132 if( k == cnt )
133 {
134 g[ j ] = i;
135 break;
136 }
137 }
138 }
139}
140
141ll sum( ll q, ll n, ll P )
142{
143 if( n < 0 ) return 0;
144 if( n == 0 ) return 1 % P;
145 if( n == 1 ) return ( 1 + q ) % P;
146 ll S;
147 if( n & 1 )
148 {
149 S = sum( q, n >> 1, P );
150 return ( S + S * pow_mod( q, n / 2 + 1, P ) % P ) % P;
151 }
152 S = sum( q, n - 1, P );
153 return ( S + pow_mod( q, n, P ) ) % P;
154}
155
156int main(int argc, char *argv[])
157{
158 // freopen("out.out","w",stdout);
159 int cas;
160 prime( );
161 scanf("%d",&cas);
162 for( int t = 1; t <= cas; t++ )
163 {
164 scanf("%I64d%I64d",&A,&K);
165 M = 1;
166 for( int i = 0; i <= K; i++ )
167 {
168 scanf("%I64d%I64d%I64d",&b[ i ],&p[ i ],&c[ i ]);
169 PC[ i ] = 1;
170 for( int j = 0; j < c[ i ]; j++ )
171 PC[ i ] *= p[ i ];
172 M *= PC[ i ];
173 }
174 N = china( b, PC, K + 1 );
175 find_g( );
176 ll seg_res, seg_ment, base;
177 for( int i = 0; i <= K; i++ )
178 {
179 if( p[ i ] == 2 )
180 {
181 if( c[ i ] == 1 ) base = 1;
182 else base = ( A % 2 == 1 ? 0 : ( 1 << ( c[ i ] - 1 ) ) );
183 }
184 else
185 {
186 base = pow_mod( g[ i ], A, PC[ i ] );
187 base = sum( base, PC[ i ] / p[ i ] * ( p[ i ] - 1 ) - 1, PC[ i ] );
188 }
189 seg_ment = N / PC[ i ];
190 seg_res = b[ i ];
191 ans = base * seg_ment % PC[ i ];
192 ll tmp = 0;
193 for( int j = 1; j <= b[ i ]; j++ )
194 {
195 tmp = ( tmp + pow_mod( j, A, PC[ i ] ) ) % PC[ i ];
196 }
197 B[ i ] = ( ans + tmp ) % PC[ i ];
198 }
199 ans = china( B, PC, K + 1 );
200 printf("Case %d: %I64d\n",t, ans % M );
201 }
202 return 0;
203}
204
|