欧拉定理（进阶） 10@亿万星辰 poj_3696最幸运的数字

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll gcd(ll a,ll b)//求最大公约数 
{
	int t;
	while((a%=b)!=0){
		t=a,a=b,b=t;
	}
	return b;
}
ll multiply(ll x, ll y,ll p)//快速乘（防爆） 
{
	ll re=0;
	while(y)
	{
		if(y&1)re=(re+x)%p;
		x=(x+x)%p;y>>=1;
	}
	return re;
}
ll power(ll x, ll y,ll p) //快速幂
{
	ll re=1;
	while(y)
	{
		if(y&1)re=multiply(re,x,p)%p;
		x=multiply(x,x,p)%p;y>>=1;
	}
	return re;
}
ll getphi(ll n)//求phi(n) 
{
	ll re=n;
	for(ll i=2;i*i<=n;++i)
	{
		if(n%i==0)re=re/i*(i-1);
		while(n%i==0)n/=i;
	}
	if(n!=1)re=re/n*(n-1);
	return re;
}
int main()
{
	char ch;
	ll num,cnt=1;
	while((ch=getchar())<'0'||ch>'9');//消非可用字符 
	while(ch!=48)
	{
		num=ch^48;
		while((ch=getchar())>='0'&&ch<='9') num=10*num+(ch^48);//快读
			ll n=9*num/gcd(1ll*8,1ll*9*num);ll x=getphi(n);
		if(gcd(10,n)!=1){printf("Case %d: 0\n",cnt);continue;}
		for(ll i=1;i*i<=x;i++)//从1~根号x寻找，头部密集查找法 
			if(x%i==0&&power(10,i,n)==1)
			{
				printf("Case %lld: %lld\n",cnt,i);
				goto end;
			}
		for(ll i=sqrt(1.0*x);i>=1;i--)//从根号x继续查找，尾部稀疏查找法 
			if(x%i==0&&power(10,x/i,n)==1)
			{
				printf("Case %lld: %lld\n",cnt,x/i);
				break;
			}
		end: ;
		cnt++;
		while((ch=getchar())<'0'||ch>'9');
	}
	return 0;
 }