• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            coreBugZJ

            此 blog 已棄。

            Color,POJ 2154

            Color
            Time Limit: 2000MS
            Memory Limit: 65536K
            Total Submissions: 3175
            Accepted: 1084

            Description

            Beads of N colors are connected together into a circular necklace of N beads (N<=1000000000). Your job is to calculate how many different kinds of the necklace can be produced. You should know that the necklace might not use up all the N colors, and the repetitions that are produced by rotation around the center of the circular necklace are all neglected.

            You only need to output the answer module a given number P.

            Input

            The first line of the input is an integer X (X <= 3500) representing the number of test cases. The following X lines each contains two numbers N and P (1 <= N <= 1000000000, 1 <= P <= 30000), representing a test case.

            Output

            For each test case, output one line containing the answer.

            Sample Input

            5
            1 30000
            2 30000
            3 30000
            4 30000
            5 30000

            Sample Output

            1
            3
            11
            70
            629

            Source

            POJ Monthly,Lou Tiancheng


            Polya,只有旋轉,沒有反射,歐拉函數優化。


             1 #include <stdio.h>
             2 #include <string.h>
             3 
             4 #define  L  50000
             5 
             6 int nPrime, prime[ L ];
             7 
             8 void initPrime() {
             9         int i, j;
            10         nPrime = 0;
            11         memset( prime, 0sizeof(prime) );
            12         for ( i = 2; i < L; ++i ) {
            13                 if( prime[ i ] == 0 ) {
            14                         prime[ nPrime++ ] = i;
            15                         for ( j = i+i; j < L; j+=i ) {
            16                                 prime[ j ] = 1;
            17                         }
            18                 }
            19         }
            20 }
            21 
            22 int phi( int n ) {
            23         int i, ans = n;
            24         for ( i = 0; (i<nPrime)&&(prime[i]*prime[i]<=n); ++i ) {
            25                 if ( n % prime[ i ] == 0 ) {
            26                         ans = ans / prime[ i ] * ( prime[ i ] - 1 );
            27                         do {
            28                                 n /= prime[ i ];
            29                         } while ( n % prime[ i ] == 0 );
            30                 }
            31         }
            32         if ( n != 1 ) {
            33                 ans = ans / n * (n-1);
            34         }
            35         return ans;
            36 }
            37 
            38 int power( int a, int b, int m ) {
            39         int t = 0, ans = 1;
            40         a %= m;
            41         while ( (1<<t) < b ) {
            42                 ++t;
            43         }
            44         while ( t >= 0 ) {
            45                 ans = ( ans * ans ) % m;
            46                 if ( (1<<t) & b ) {
            47                         ans = ( ans * a ) % m;
            48                 }
            49                 --t;
            50         }
            51         return ans;
            52 }
            53 
            54 int solve( int n, int p ) {
            55         int i, ans = 0;
            56         for ( i = 1; i*< n; ++i ) {
            57                 if ( n % i == 0 ) {
            58                         ans = ( ans + phi( i   ) % p * power( n, n/i-1, p ) ) % p;
            59                         ans = ( ans + phi( n/i ) % p * power( n, i-1,   p ) ) % p;
            60                 }
            61         }
            62         if ( i*== n ) {
            63                 ans = ( ans + phi( i ) % p * power( n, i-1, p ) ) % p;
            64         }
            65         return ans;
            66 }
            67 
            68 int main() {
            69         int td, n, p;
            70         initPrime();
            71         scanf( "%d"&td );
            72         while ( td-- > 0 ) {
            73                 scanf( "%d%d"&n, &p );
            74                 printf( "%d\n", solve( n, p ) );
            75         }
            76         return 0;
            77 }
            78 



            posted on 2011-04-18 22:24 coreBugZJ 閱讀(388) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            久久免费高清视频| 久久影院综合精品| 亚洲中文字幕伊人久久无码| 人人狠狠综合久久亚洲高清| 精品久久久久久久久免费影院| 无码人妻少妇久久中文字幕蜜桃| 国产国产成人精品久久| 欧美日韩精品久久久免费观看| 久久久久人妻一区二区三区| 伊人久久大香线蕉精品| 国产精品久久久久久久app| 久久成人精品视频| 久久精品中文字幕一区| 亚洲欧美日韩精品久久| 欧美熟妇另类久久久久久不卡| 精品久久久久久无码免费| 久久婷婷五月综合97色| 亚洲精品无码久久不卡| 国产精品成人久久久久久久| 亚洲中文久久精品无码ww16 | 久久青青草视频| 国产亚洲美女精品久久久| 国内精品人妻无码久久久影院| 亚洲一区精品伊人久久伊人| 久久电影网| 久久久噜噜噜久久| 99久久国产综合精品网成人影院| 久久精品国产久精国产思思| 久久久亚洲AV波多野结衣 | 无码人妻久久一区二区三区蜜桃 | 欧美大香线蕉线伊人久久| 久久久久久国产a免费观看黄色大片| 99久久免费只有精品国产| 亚洲国产精品久久久久网站| 青青草原综合久久| 国产成人综合久久精品尤物| 国内精品久久久久久久久| 国産精品久久久久久久| 日产久久强奸免费的看| 久久人人爽人人爽人人片AV麻烦| 精品久久久一二三区|