#POJ3696# The Luckiest number

2019-11-11 01:53:41

字體：大中小

供稿：網(wǎng)友

The Luckiest number

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'.InputThe 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.OutputFor 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

811160Sample OutputCase 1: 1Case 2: 2Case 3: 0
題意：
給出一個數(shù)L(L<2,000,000,000)，找一個最小的L的倍數(shù)，使其乘積的每個數(shù),字都是8，求這個乘積的位數(shù)。
設(shè)此乘積位數(shù)為x，倍數(shù)為k
則有
(10 ^ x - 1) * 8 / 9 = k * L
      10 ^ x - 1 = 9 / 8 * k * L
令 m = 9 * L / gcd (L , 8), y = k * gcd (L , 8) / 8
若此L有解，則
1：滿足上式
2：k為整數(shù)
3：y為整數(shù)
假設(shè)1，2成立，則3若成立，L即有解
則有
(10 ^ x - 1) % m = 0
 10 ^ x % m = 1
由歐拉公式得： 若上式有解，則必有10與m互素，且x = φ(m)
φ(m)肯定為L有解的一個倍數(shù)，但不一定是最小的，x的最小值肯定為φ(m)的約數(shù)
于是窮舉約數(shù)檢查是否符合10 ^ x % m = 1，找到最小x
注意：
1：枚舉時只枚舉到sqrt(φ(m))再倒回去通過前半段算出后半段即可，節(jié)省時間
2：此題檢驗時由于是10的指數(shù)，容易溢出，所以快速冪相乘時改成了加法做乘法，倍增加法，原理同倍增快速冪
Code:
Status Accepted
Time 156ms
Memory 1728kB
Length 1063
Lang C++
Submitted 2017-02-07 17:20:08
Shared 
#include<iostream>#include<cstdio>#include<cmath>using namespace std;typedef long long LL;LL gcd(LL A,LL B){return B==0?A:gcd(B,A%B);}LL mul(LL a, LL b, LL mod){//考慮換成m個10相加，倍增+mod	LL rt=0;	while(b){		if(b&1)	rt=(rt+a)%mod;		a=(a<<1)%mod;		b>>=1;	}	return rt;}LL qmul(LL a, LL b, LL mod){	LL s=1,tmp=a;	while(b){		if(b&1)	s=mul(s,tmp,mod);		tmp=mul(tmp,tmp,mod);		b>>=1;	}	return s;}LL Euler(LL n){	LL m=(int)sqrt(n+0.5);	LL rt=n;	for(LL i=2; i<=m; ++i)if(n%i==0){		rt=rt/i*(i-1);		while(n%i==0)n/=i;	}	if(n>1)rt=rt/n*(n-1);	return rt;}int main(){	int tot=0,d;	LL L,m;	while(scanf("%I64d",&L)&&L){		m=9*L/gcd(L,8);		printf("Case %d: ",++tot);		d=gcd(10,m);		if(d==1){			LL phi=Euler(m);			LL ans=phi;			LL p=sqrt((double)phi);			bool kk=0;			for(int i=1; i<=p; ++i)if(phi%i==0&&qmul(10,i,m)==1){				ans=i,kk=1;				break;			}			if(!kk){				for(int i=p; i>=2; --i)if(phi%i==0&&qmul(10,phi/i,m)==1){					ans=phi/i,kk=1;					break;				}			}			printf("%I64d/n",ans);		}		else {printf("0/n");}	}}