• <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 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久婷婷五月综合97色直播|
久久精品国产一区|
99久久综合国产精品免费|
亚洲精品无码久久不卡|
久久久一本精品99久久精品66|
久久国产精品99久久久久久老狼
|
日产精品久久久久久久性色|
国产精品久久久久jk制服|
国产农村妇女毛片精品久久|
久久精品中文字幕大胸|
成人资源影音先锋久久资源网|
亚洲精品99久久久久中文字幕
|
国产精品热久久毛片|
色8激情欧美成人久久综合电|
香蕉久久av一区二区三区|
久久精品视频免费|
久久久国产99久久国产一|
伊人久久综在合线亚洲2019
|
青青青国产精品国产精品久久久久
|
日产精品久久久久久久性色|
国产亚洲色婷婷久久99精品91|
久久青青草原亚洲av无码app|
欧美日韩成人精品久久久免费看|
7777久久亚洲中文字幕|
久久99这里只有精品国产|
91久久精品国产成人久久|
精品国产一区二区三区久久久狼|
青青草原综合久久大伊人|
久久人人爽人人爽AV片|
久久99精品国产99久久|
久久久久99精品成人片试看|
久久久久高潮综合影院|
97香蕉久久夜色精品国产|
天天综合久久一二三区|
色婷婷狠狠久久综合五月|
久久婷婷色综合一区二区|
国产日韩久久久精品影院首页|
久久久久国产精品|
91精品国产91久久久久久蜜臀|
久久91精品国产91久久小草|
国产精品久久久久久久久|