• <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 已棄。
            

            




            
	
					
	
            
		
            
			POJ 3696 The Luckiest number
		
            
		
              1/*
              2POJ 3696 The Luckiest number
              3
              4
              5----問題描述：
              6
              7Chinese people think of '8' as the lucky digit. Bob also likes digit '8'. Moreover, Bob has his own lucky number L. Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of L and consist of only digit '8'.
              8
              9
             10----輸入：
             11
             12The input consists of multiple test cases. Each test case contains exactly one line containing L(1 ≤ L ≤ 2,000,000,000).
             13
             14The last test case is followed by a line containing a zero.
             15
             16
             17----輸出：
             18
             19For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the length of Bob's luckiest number. If Bob can't construct his luckiest number, print a zero.
             20
             21
             22----樣例輸入：
             23
             248
             2511
             2616
             270
             28
             29
             30----樣例輸出：
             31
             32Case 1: 1
             33Case 2: 2
             34Case 3: 0
             35
             36
             37----分析：
             38
             39（轉自網上）
             40
             41題意：給一個數N(1<=N<=2000000000);問是否存在N的倍數M，且M的各個位全部由8組成，如果存在多個取最小的 M 并輸出M由幾個8組成。
             42
             43解題思路：因為M全部由8組成，即M=（10^x -1）*8/9=k*N;
             44
             45則    (10^x-1)*8/gcd(8,N)=9*k*N/gcd(8,N);
             46
             47令p=8/gcd(8,N);        q=9*N/gcd(8,N);    即    (10^x-1)*p=k*q;
             48
             49由于p和q互質，則(10^x-1)%q==0;
             50
             51根據同余定理可知，10^x ≡1（mod q）
             52
             53根據歐拉定理可知當gcd(a,b)==1時，a^φ(b)≡1(mod b);
             54
             55即可得出：當gcd(10,q)==1時    10^φ(q)≡1(mod q)   即通過枚舉φ(q)的因子（最小因子）就能得出結果
             56
             57由于N比較大，因此采用long long 型。同時做一個素數表。
             58
             59在進行冪求模運算的時候可以采用快速冪的方法。
             60
             61由于在進行快速冪求模的時候數據會超出long long 的表示范圍，因此要進行優化。
             62
             63
             64*/
             65
             66
             67/**********************************************
             68版本一：
             69*/
             70
             71#include <iostream>
             72#include <cstdio>
             73#include <cstring>
             74
             75using namespace std;
             76
             77typedef  __int64  Lint;
             78
             79#define  LP  45000
             80int  nprime;
             81Lint prime[ LP ];
             82
             83#define  LF  128
             84int  nf;
             85Lint f[ LF ];
             86
             87void init_prime() {
             88        int i, j;
             89        nprime = 0;
             90        memset( prime, 0, sizeof(prime) );
             91        for ( i = 2; i < LP; ++i ) {
             92                if ( 0 == prime[ i ] ) {
             93                        prime[ nprime++ ] = i;
             94                        for ( j = i+i; j < LP; j += i ) {
             95                                prime[ j ] = 1;
             96                        }
             97                }
             98        }
             99}
            100
            101void calc_f( Lint n ) {
            102        int i;
            103        nf = 0;
            104        for ( i = 0; (i < nprime)&&(prime[i]*prime[i] <= n); ++i ) {
            105                while ( n % prime[ i ] == 0 ) {
            106                        f[ nf++ ] = prime[ i ];
            107                        n /= prime[ i ];
            108                }
            109        }
            110        if ( 1 < n ) {
            111                f[ nf++ ] = n;
            112        }
            113}
            114
            115Lint gcd( Lint a, Lint b ) {
            116        Lint t;
            117        while ( 0 != b ) {
            118                t = a;
            119                a = b;
            120                b = t % b;
            121        }
            122        return a;
            123}
            124        // a * b % m
            125Lint mul_mod( Lint a, Lint b, Lint m ) {
            126        Lint s = 0;
            127        a %= m;
            128        while ( 0 != b ) {
            129                if ( 0 != (1 & b) ) {
            130                        s += a;
            131                        if ( s >= m ) {
            132                                s -= m;
            133                        }
            134                }
            135                a <<= 1;
            136                if ( a >= m ) {
            137                        a -= m;
            138                }
            139                b >>= 1;
            140        }
            141        return s;
            142}
            143        // a ^ b % m
            144Lint pow_mod( Lint a, Lint b, Lint m ) {
            145        Lint s = 1;
            146        a %= m;
            147        while ( 0 != b ) {
            148                if ( 0 != (1 & b) ) {
            149                        s = mul_mod( s, a, m );
            150                }
            151                a = mul_mod( a, a, m );
            152                b >>= 1;
            153        }
            154        return s;
            155}
            156        // 歐拉
            157Lint phi( Lint n ) {
            158        Lint s = n;
            159        int i;
            160        for ( i = 0; (i < nprime)&&(prime[i]*prime[i] <= n); ++i ) {
            161                if ( n % prime[ i ] == 0 ) {
            162                        s = s / prime[ i ] * (prime[ i ] - 1);
            163                        do {
            164                                n /= prime[ i ];
            165                        }             while ( n % prime[ i ] == 0 );
            166                }
            167        }
            168        if ( 1 < n ) {
            169                s = s / n * (n - 1);
            170        }
            171        return s;
            172}
            173
            174Lint solve( Lint n ) {
            175        Lint m = 9 * n / gcd(8, n);
            176        if ( 1 != gcd(10, m) ) {
            177                return 0;
            178        }
            179
            180        Lint ph = phi(m);
            181        Lint s  = ph;
            182        int  i;
            183        bool down = true;
            184        while ( down ) {
            185                down = false;
            186                calc_f(ph);
            187                for ( i = 0; i < nf; ++i ) {
            188                        if ( (pow_mod(10, ph/f[i], m) == 1) && (ph/f[i] < s) ) {
            189                                s = ph / f[ i ];
            190                                down = true;
            191                        }
            192                }
            193                ph = s;
            194        }
            195        return s;
            196}
            197
            198int main() {
            199        int td = 0, n;
            200        init_prime();
            201        while ( (1 == scanf("%d", &n)) && (0 < n) ) {
            202                printf( "Case %d: %I64d\n", ++td, solve(n) );
            203        }
            204        return 0;
            205}
            206
            
		
            
			posted on 2012-06-01 21:32 coreBugZJ 閱讀(721) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、Mathematics 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



蜜桃麻豆WWW久久囤产精品|
亚洲精品高清久久|
久久本道久久综合伊人|
蜜桃麻豆www久久|
久久精品国产免费一区|
avtt天堂网久久精品|
亚洲国产精品无码成人片久久|
漂亮人妻被中出中文字幕久久|
亚洲人成网站999久久久综合
|
亚洲午夜久久久久久久久久|
一本色综合久久|
波多野结衣AV无码久久一区|
久久99久久99精品免视看动漫
|
无码8090精品久久一区|
中文字幕无码久久久|
久久伊人精品一区二区三区|
久久精品国产久精国产果冻传媒|
国内精品久久久久影院薰衣草|
无码精品久久久久久人妻中字|
久久99国产精品久久|
久久av免费天堂小草播放|
亚洲欧洲精品成人久久奇米网|
久久午夜夜伦鲁鲁片免费无码影视|
狠狠综合久久AV一区二区三区|
国产午夜免费高清久久影院|
国产成人精品久久一区二区三区av|
久久人人超碰精品CAOPOREN|
久久WWW免费人成一看片|
国产福利电影一区二区三区久久久久成人精品综合
|
亚洲成色www久久网站夜月|
好久久免费视频高清|
亚洲午夜福利精品久久|
av无码久久久久久不卡网站|
久久综合伊人77777|
www久久久天天com|
久久亚洲日韩看片无码|
色综合久久天天综合|
99久久精品免费看国产一区二区三区
|
久久精品人人做人人爽电影蜜月|
久久99精品国产麻豆不卡|
久久精品国产亚洲av麻豆色欲|