HDU 2462 - The Luckiest number（歐拉定理）

The Luckiest number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1935    Accepted Submission(s): 603

Problem Description

Chinese 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'.

Input

The input consists of multiple test cases. Each test case contains exactly one line containing L(1 ≤ L ≤ 2,000,000,000).

The last test case is followed by a line containing a zero.

Output

For 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.

Sample Input

8

11

16

Sample Output

Case 1: 1

Case 2: 2

Case 3: 0

Source

2008 Asia Hefei Regional Contest Online by USTC

歐拉定理：a^x

 1(mod m),那麼 x = euler(m);

推導：

（10^x - 1）/ 9 * 8  ==  n * p ; 則10^x  - 1 == n * p / 8 * 9;

設m == 9*n / gcd(n,8);

那麼（10^x - 1）== m * p' ; 可以得到10 ^ x 

1 (mod m);

可以知道，當m 和 10不互質的時候，肯定不符合答案；

然後x == euler(m),然後答案就是滿足這個方程的是euler(m)的因數的最小的值；

在找滿足方程的euler(m)的最小因數的時候為了防止逾時，可以從通路到一半的位置，之後再進行除法進而判斷後面的數的情況；

  需要注意的是，對于10^x，由于m太大，直接快速幂相乘的時候會超long long。，需要乘法轉化一下。

參考的代碼：

#include <bits/stdc++.h>
using namespace std;
#define clr(a) memset(a,0,sizeof(a))
#define line cout<<"-----------------"<<endl;

typedef long long ll;
const int maxn = 1e5+10;
const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int N = 1010;

ll gcd(ll a,ll b){
	return b == 0 ? a : gcd(b , a%b);
}
ll Euler(ll n){//歐拉函數模闆
    ll ans = 1;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0){
            n /= i;
            ans *= (i - 1);
            while(n % i == 0){
                n /= i;
                ans *= i;
            }
        }
    }
    if(n > 1) ans *= (n-1);
    return ans ;
}
ll Mul(ll x , ll y , ll mod){//快速幂取模模闆
	ll ans = 0;
	while(y){
		if(y & 1){
			ans = (ans + x) % mod;
		}
		x = x * 2 % mod;
		y >>= 1;
	}
	return ans ;
}
ll pow_mod(ll x , ll n , ll mod ){
	ll ans = 1;
	ll t = x % mod ;
	while(n) {
		if(n & 1){
			ans = Mul(ans , t, mod);
		}
		t = Mul(t , t , mod);
		n >>= 1 ;
	}
	return ans ;
}

int main(){
	int cas = 1;
	ll n,ans;
	while(scanf("%lld",&n)!=EOF && n){
		ll m = n / gcd(n , 8) * 9;
		if(gcd(10 , m) != 1)
			ans = 0;
		else{
			ll cnt = Euler(n);
			ans = 1e18 ;
			for( ll i = 1 ; i * i <= cnt ; i ++){
				if( cnt % i == 0 ){
					if( pow_mod (10 , i , m) == 1)
						ans = min(ans , i);
					if( pow_mod(10 , cnt/i ,m) == 1)
						ans = min(ans , cnt/i);
				}
			}
		}
		printf("Case %d: %lld\n", cas ++ , ans );
	}
	return 0;
}
           

自己的代碼：

#include <bits/stdc++.h>
using namespace std;
#define clr(a) memset(a,0,sizeof(a))
#define line cout<<"-----------------"<<endl;

typedef long long ll;
const int maxn = 1e5+10;
const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int N = 1010;

vector<ll> ve;

ll gcd(ll a,ll b){
	return b == 0 ? a : gcd(b , a%b);
}
void get_prime(ll n){
	for(ll i = 1 ; i * i <= n ; i++){
		if(n % i == 0){
			ve.push_back(i);
			if(i * i != n)
				ve.push_back(n/i);
		}
	}
}
ll Euler(ll n){//歐拉函數模闆
    ll ans = 1;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0){
            n /= i;
            ans *= (i - 1);
            while(n % i == 0){
                n /= i;
                ans *= i;
            }
        }
    }
    if(n > 1) ans *= (n-1);
    return ans ;
}
//下面兩個函數是為了防止 快速幂爆 long long 
ll Mul(ll x , ll y , ll mod){//快速幂取模模闆
	ll ans = 0;
	while(y){
		if(y & 1){
			ans = (ans + x) % mod;
		}
		x = x * 2 % mod;
		y >>= 1;
	}
	return ans ;
}
ll pow_mod(ll x , ll n , ll mod ){
	ll ans = 1;
	ll t = x % mod ;
	while(n) {
		if(n & 1){
			ans = Mul(ans , t, mod);
		}
		t = Mul(t , t , mod);
		n >>= 1 ;
	}
	return ans ;
}

int main(){
	int cas = 1;
	ll n,ans;
	while(scanf("%lld",&n)!=EOF && n){
		ve.clear();
		ll m = n / gcd(n , 8) * 9;
		if(gcd(10 , m) != 1)
			ans = 0;
		else{
			ans = Euler(m);
			get_prime(ans);//講ans因數分解的結果儲存
			sort(ve.begin(),ve.end());//從小大大排序
			for(ll i=0;i<ve.size();i++){
				if( pow_mod(10ll , ve[i] ,m) == 1 ){//如果滿足要求
					ans = ve[i];
					break;
				}
			}
		}
		printf("Case %d: %lld\n", cas ++ , ans );
	}
	return 0;
}