poj 2888 Magic Bracelet

poj 2888 Magic Bracelet

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <vector>#include <queue>using namespace std;#define LL long long#define eps 1e-6#define inf 0x3f3f3f3f#define MP make_pair#define mnx 50005#define mod 9973int pri[mnx], tot;bool isnot[mnx];void init(){    for( int i = 2; i < mnx; ++i ){        if( !isnot[i] ){ pri[tot++] = i;        }        for( int j = 0; j < tot && i * pri[j] < mnx; ++j ){ isnot[i*pri[j]] = 1; if( i % pri[j] == 0 )     break;        }    }}int phi( int x ){    int ret = x;    for( int i = 0; i < tot && pri[i] * pri[i] <= x; ++i ){        if( x % pri[i] == 0 ) ret = ret / pri[i] * ( pri[i] - 1 );        while( x % pri[i] == 0 ) x /= pri[i];    }    if( x > 1 ) ret = ret / x * ( x - 1 );    return ret % mod;}int n, m;struct Matrix{    int g[12][12];    Matrix operator * ( const Matrix &b ) const {        Matrix ret;        memset( ret.g, 0, sizeof(ret.g) );        for( int i = 1; i <= m; ++i ) for( int j = 1; j <= m; ++j ){     for( int k = 1; k <= m; ++k )         ret.g[i][j] += g[i][k] * b.g[k][j];     ret.g[i][j] %= mod; }        return ret;    }};Matrix qpow( Matrix x, int k ){    Matrix ret;    memset( ret.g, 0, sizeof(ret.g) );    for( int i = 1; i <= m; ++i )        ret.g[i][i] = 1;    while( k ){        if( k & 1 ) ret = ret * x;        x = x * x;        k >>= 1;    }    return ret;}int qpow( int x, int k ){    int ret = 1;    x %= mod;    while( k ){        if( k & 1 ) ret = ret * x % mod;        x = x * x % mod;        k >>= 1;    }    return ret;}int k;Matrix a;int gao( int x ){    int res = 0;    Matrix ret = qpow( a, x );    for( int i = 1; i <= m; ++i )        res += ret.g[i][i];    return res % mod;}void solve(){    int ans = 0;    int i;    for( i = 1; i * i < n; ++i ){        if( n % i == 0 ){ int tmp = n / i; ans = ( ans + phi(tmp) * gao(i) ) % mod; ans = ( ans + phi(i) * gao(tmp) ) % mod;        }    }    if( i * i == n )        ans = ( ans + phi(i) * gao(i) ) % mod;    int inv = qpow( n % mod, mod - 2 ) % mod;    ans = ( ans * inv ) % mod;    printf( "%dn", ans );}int main(){   // freopen( "tt.txt", "r", stdin );    int cas;    init();    scanf( "%d", &cas );    while( cas-- ){        scanf( "%d%d%d", &n, &m, &k );        for( int i = 1; i <= m; ++i ) for( int j = 1; j <= m; ++j )     a.g[i][j] = 1;        for( int i = 0; i < k; ++i ){ int u, v; scanf( "%d%d", &u, &v ); a.g[u][v] = a.g[v][u] = 0;        }        solve();    }    return 0;}