• <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

            狠狠色丁香久久综合五月| 久久精品午夜一区二区福利 | 精品久久一区二区| 夜夜亚洲天天久久| 久久99精品国产麻豆宅宅| 午夜精品久久久久久99热| 国产精品成人99久久久久91gav| 亚洲人AV永久一区二区三区久久| 久久综合噜噜激激的五月天| 久久伊人影视| 天天久久狠狠色综合| 久久国产乱子伦免费精品| 久久99国产精品99久久| 久久久久波多野结衣高潮| 亚洲乱亚洲乱淫久久| 久久久久久国产a免费观看黄色大片| 国产精品久久毛片完整版| 亚洲国产另类久久久精品黑人| 99久久精品无码一区二区毛片| 亚洲愉拍99热成人精品热久久 | 麻豆亚洲AV永久无码精品久久| 伊人久久综在合线亚洲2019 | 久久久精品人妻一区二区三区蜜桃| AV狠狠色丁香婷婷综合久久| 国产亚洲欧美精品久久久| 久久久久久伊人高潮影院| 久久av免费天堂小草播放| 欧美亚洲日本久久精品| 色综合久久久久综合99| 精品精品国产自在久久高清| 精品无码久久久久久尤物| 97精品依人久久久大香线蕉97| 一本色道久久综合| 性高湖久久久久久久久AAAAA| 久久精品国产99国产精品| 久久成人小视频| 亚洲午夜久久久久久久久电影网| 亚洲欧洲久久av| 久久人人爽人人爽人人片AV高清| 色综合久久天天综线观看| 伊人久久大香线蕉精品不卡 |