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





            
	    
    




            






            

				

            


    
    







            
	   
	



午夜精品久久久久久|
狠狠色婷婷久久综合频道日韩
|
91精品国产9l久久久久|
久久国产成人午夜aⅴ影院|
日本欧美久久久久免费播放网|
2020久久精品亚洲热综合一本|
日韩电影久久久被窝网|
亚洲国产天堂久久久久久|
国产亚洲精品久久久久秋霞|
少妇无套内谢久久久久|
久久久久久久免费视频|
久久久国产精华液|
久久久久久伊人高潮影院|
久久精品a亚洲国产v高清不卡|
粉嫩小泬无遮挡久久久久久|
成人a毛片久久免费播放|
国内精品久久久久久久coent
|
久久国产精品成人片免费|
99久久综合狠狠综合久久止|
精品人妻伦一二三区久久
|
性高湖久久久久久久久AAAAA
|
久久久久久久久久久久久久|
久久精品aⅴ无码中文字字幕不卡|
色欲综合久久躁天天躁|
88久久精品无码一区二区毛片|
久久久无码精品亚洲日韩蜜臀浪潮|
99久久婷婷国产综合亚洲|
日韩精品久久久久久久电影|
国产高清美女一级a毛片久久w|
国产精品久久久久久影院|
少妇久久久久久久久久|
久久93精品国产91久久综合|
亚洲精品视频久久久|
久久国产色AV免费看|
91性高湖久久久久|
亚洲国产精品18久久久久久|
国产Av激情久久无码天堂|
亚洲国产精品综合久久一线|
91精品国产综合久久久久久|
久久夜色精品国产www|
久久久精品2019免费观看|