The Luckiest number

811160Sample Output
Case 1: 1Case 2: 2Case 3: 0
題意：
給出一個(gè)數(shù)L(L<2,000,000,000)，找一個(gè)最小的L的倍數(shù)，使其乘積的每個(gè)數(shù),字都是8，求這個(gè)乘積的位數(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(zhǎng)有解的一個(gè)倍數(shù)，但不一定是最小的，x的最小值肯定為φ(m)的約數(shù)
于是窮舉約數(shù)檢查是否符合10 ^ x % m = 1，找到最小x
注意：
1：枚舉時(shí)只枚舉到sqrt(φ(m))再倒回去通過(guò)前半段算出后半段即可，節(jié)省時(shí)間
2：此題檢驗(yàn)時(shí)由于是10的指數(shù)，容易溢出，所以快速冪相乘時(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個(gè)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");}	}}