「POJ3696」The Luckiest Number

题意：给定一个正整数 $L$，$L\leq 2\times10^9$。

问至少多少个 $8$ 连在一起组成的自然数是 $L$ 的倍数。

$x$ 个 $8$ 连在一起组成的正整数可写作 $\frac{8(10 ^x -1)}{9}$。题目要求我们求最小 $x$，使 $L|\frac{8(10 ^x -1)}{9}$。设 $d=\gcd(L,8)$。

$$L| \frac{8(10 ^x -1)}{9} \longleftrightarrow 9L| 8(10^x -1) \longleftrightarrow \frac{9L}{d} |10 ^x-1 \longleftrightarrow 10 ^x \equiv 1\bmod \frac{9L}{d}$$

其中第二步到第三部的转换，因为 $\frac{8}{d}$ 为整数，所以只会为 $1,2,4,8$，与 $9$ 互质，而 $\frac{L}{d}$ 与 $\frac{8}{d}$ 互质，故右边可再除以一个 $\frac{8}{d}$。

引理：

若正整数 $a,n$ 互质，则满足 $a ^x \equiv 1\bmod n$ 的最小正整数 $x_0$ 是 $\varphi(n)$ 的约数。

然后直接枚举其约数，一一检验即可。

code:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long gcd(long long a,long long b)
{
 	if(b==0)
		return a;
 	return gcd(b,a%b);
}
long long phi(long long x)
{
 	long long ans=x;
 	for(int i=2;i*i<=x;i++)
 		if(x%i==0)
 		{
 			ans=ans/i*(i-1);
 			while(x%i==0)
 				x/=i;
 		}
 	if(x>1)
 		ans=ans/x*(x-1);
 	return ans;
}
long long power(long long a,long long b,long long p)
{
 	long long ans=1;
 	for(;b;b>>=1)
 	{
 		if(b&1)
 			ans=ans*a%p;
 		a=a*a%p;
 	}
 	return ans%p;
}
long long l,d,n,p,r,ans,cnt;
int main()
{
 	while(scanf("%lld",&l)!=EOF&&l)
 	{
 		cnt++;
 		ans=1e9;
 		d=0;
 		n=0;
 		p=0;
 		r=0;
 		d=gcd(l,(long long)8);
 		n=9*l/d;
 		r=phi(n);
 		for(long long i=1;i*i<=r;i++)
 		{
 			if(r%i==0)
 			{
 				if(power(10,i,n)==1)
 					ans=min(ans,i);
 				long long j=r/i;
 				if(i==j)
 					continue;
 				if(power(10,j,n)==1)
 					ans=min(ans,j);
 			}
 		}
 		if(ans==1e9)
 			ans=0;
 		printf("Case %lld: %lld\n",cnt,ans);
 	}
    return 0;
}