题意:
给一个L,求长度最小的全8数满足该数是L的倍数。
分析:
转化为求方程a^x==1modm。之后就是各种数学论证了。
代码:
//poj 3696
//sep9
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll L;
ll factor[65536];ll mul(ll x,ll y,ll p)
{ll ret=0;while(y){if(y&1)ret=(ret+x)%p;x=(x+x)%p;y>>=1;}return ret;
}ll pow(ll x,ll n,ll m)
{ll ret=1;x%=m;while(n){if(n&1)ret=mul(ret,x,m);x=mul(x,x,m);n>>=1;}return ret;
}ll euler(ll n)
{ll ret=n;for(ll i=2;i*i<=n;++i)if(n%i==0){ret=ret/i*(i-1);while(n%i==0)n/=i;}if(n>1)ret=ret/n*(n-1);return ret;
}ll cal()
{ll m=L*9;for(int i=0;i<3;++i)if(m%2==0)m/=2;elsebreak; if(m%2==0||m%5==0)return 0;ll phi=euler(m);int idx=0;for(ll i=1;i*i<=phi;++i)if(phi%i==0)factor[idx++]=i,factor[idx++]=phi/i; sort(factor,factor+idx);for(int i=0;i<idx;++i)if(pow(10,factor[i],m)==1)return factor[i];
}int main()
{int cases=0;while(scanf("%I64d",&L)==1&&L){printf("Case %d: ",++cases);printf("%I64d\n",cal());} return 0;
}