• <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 閱讀(737) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、Mathematics 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



99久久精品费精品国产|
香蕉久久夜色精品国产小说|
久久无码国产专区精品|
99久久国产精品免费一区二区|
少妇精品久久久一区二区三区|
久久人人爽人人爽人人片AV不|
国产精品久久久久久一区二区三区|
国产精品日韩欧美久久综合|
久久人人爽人人爽人人片av麻烦|
国产精品久久一区二区三区|
日韩精品久久久久久久电影|
精品国产一区二区三区久久|
久久国产劲爆AV内射—百度|
成人午夜精品久久久久久久小说
|
久久永久免费人妻精品下载|
精品综合久久久久久97超人|
亚洲AV无码久久精品狠狠爱浪潮|
国产三级观看久久|
久久99国产精品久久久|
日韩精品久久无码中文字幕|
欧美一区二区久久精品|
久久精品国产亚洲精品|
99久久婷婷国产一区二区|
99国产欧美久久久精品蜜芽|
99久久精品免费看国产一区二区三区|
91久久精品电影|
久久91精品国产91久久户|
99久久人妻无码精品系列|
久久夜色精品国产噜噜亚洲AV|
欧美伊人久久大香线蕉综合|
日本五月天婷久久网站|
久久亚洲熟女cc98cm|
久久久久久久免费视频|
狠狠色丁香婷婷久久综合五月|
色8激情欧美成人久久综合电|
欧美日韩中文字幕久久久不卡
|
国产精品久久久天天影视|
99久久这里只有精品|
久久综合久久综合九色|
国产无套内射久久久国产|
久久久久亚洲精品无码网址
|