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

            久久国产美女免费观看精品| 久久无码人妻一区二区三区午夜| 国产精品综合久久第一页| 青青草原综合久久大伊人精品| 91久久精品电影| 久久人与动人物a级毛片| 久久久久亚洲AV无码网站| 国产精品热久久无码av| 久久亚洲私人国产精品| 久久精品亚洲男人的天堂| 97久久国产亚洲精品超碰热 | 久久精品国产亚洲AV不卡| 久久亚洲精品国产精品| 国产精品久久久久一区二区三区| 99久久99久久久精品齐齐| 香蕉99久久国产综合精品宅男自| 国产精品视频久久久| 久久久久久久久久久免费精品| 久久久久久久人妻无码中文字幕爆 | 中文字幕精品久久| 国产香蕉97碰碰久久人人| 亚洲国产香蕉人人爽成AV片久久 | 久久婷婷激情综合色综合俺也去| 99热都是精品久久久久久| 7777久久亚洲中文字幕| 日本强好片久久久久久AAA| 亚洲精品tv久久久久| 国产精品熟女福利久久AV| 国产精品女同一区二区久久| 久久精品国产亚洲AV无码娇色| 思思久久精品在热线热| 久久天天躁狠狠躁夜夜av浪潮| 国产精品免费久久| 国产精品久久国产精品99盘| 精品久久久久久中文字幕人妻最新| 一本色道久久综合狠狠躁篇| 久久精品国产福利国产秒| 97久久精品午夜一区二区| 91精品国产91久久| 国产真实乱对白精彩久久| 亚洲国产天堂久久综合|