• <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（轉(zhuǎn)自網(wǎng)上）
             40
             41題意：給一個數(shù)N(1<=N<=2000000000);問是否存在N的倍數(shù)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互質(zhì)，則(10^x-1)%q==0;
             50
             51根據(jù)同余定理可知，10^x ≡1（mod q）
             52
             53根據(jù)歐拉定理可知當gcd(a,b)==1時，a^φ(b)≡1(mod b);
             54
             55即可得出：當gcd(10,q)==1時    10^φ(q)≡1(mod q)   即通過枚舉φ(q)的因子（最小因子）就能得出結(jié)果
             56
             57由于N比較大，因此采用long long 型。同時做一個素數(shù)表。
             58
             59在進行冪求模運算的時候可以采用快速冪的方法。
             60
             61由于在進行快速冪求模的時候數(shù)據(jù)會超出long long 的表示范圍，因此要進行優(yōu)化。
             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 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



四虎亚洲国产成人久久精品|
国产精品美女久久久久网|
久久男人AV资源网站|
中文字幕一区二区三区久久网站|
久久99精品综合国产首页|
久久久久99精品成人片三人毛片|
久久久久免费精品国产|
久久久久综合网久久|
久久精品aⅴ无码中文字字幕不卡|
精品国产乱码久久久久久郑州公司|
国产精久久一区二区三区|
亚洲国产另类久久久精品|
狠狠人妻久久久久久综合|
久久夜色精品国产亚洲|
久久99久国产麻精品66|
日日狠狠久久偷偷色综合96蜜桃|
久久亚洲精品人成综合网|
久久国产精品无|
久久国产成人午夜AV影院|
国产精品对白刺激久久久|
久久久久久久精品妇女99|
久久久久亚洲AV成人网人人网站|
久久精品黄AA片一区二区三区
|
久久精品国产亚洲AV香蕉|
欧美激情精品久久久久久久九九九|
久久国产高清字幕中文|
久久久久女人精品毛片|
久久丫忘忧草产品|
久久久久亚洲精品日久生情
|
亚洲性久久久影院|
久久中文字幕无码专区|
亚洲国产精品久久久久久|
久久精品一区二区|
一级做a爰片久久毛片人呢|
久久最新精品国产|
国产69精品久久久久99尤物|
97久久久精品综合88久久|
久久国产乱子伦精品免费强|
天天爽天天爽天天片a久久网|
国产精品久久久亚洲|
99久久这里只有精品|