技术提供微信网站开发,装修设计培训学费多少钱,优秀企业网站建设哪家服务好,网站代码查询正题
题目链接:http://poj.org/problem?id3696 题目大意
求多少个8连在一起是LL的倍数。解题思路将x个8连在一起分解一下
10x#x2212;19 role=presentation10x−1910x−19 那么就是 L|2∗(10x−1)9L|2∗(10x−1)9dgcd(L,8)dgcd(L,8)分解一下 9…正题
题目链接:http://poj.org/problem?id3696 题目大意
求多少个8连在一起是LLL的倍数。解题思路将x个8连在一起分解一下
10x#x2212;19" role="presentation">10x−1910x−19\frac{10^x-1}{9} 那么就是
L|2∗(10x−1)9L|2∗(10x−1)9
L|\frac{2*(10^x-1)}{9} dgcd(L,8)dgcd(L,8)d=gcd(L,8) 分解一下 9Ld|10x−19Ld|10x−1
\frac{9L}{d}|10^x-1 然后 10x≡1(mod 9Ld)10x≡1(mod9Ld)
10^x\equiv1(mod\ \ \frac{9L}{d}) 根据欧拉定理若gcd(a,n)1gcd(a,n)1gcd(a,n)=1 ax≡1(mod n)ax≡1(modn)a^x\equiv1(mod\ \ n)时xxx是#x03C6;(n)" role="presentation">φ(n)φ(n)\varphi(n)的约数。 所以我们就可以枚举φ(n)φ(n)\varphi(n)的约数计算前面的答案。code
#includecstdio
#includealgorithm
#define ll long long
using namespace std;
ll L,tot;
ll gcd(ll a,ll b)
{return a0?b:gcd(b%a,a);}
ll mul(ll x,ll k)//慢速乘免爆炸
{ll ans0;while(k){if (k1) ans(ansx)%L;x(x*2)%L;k1;}return ans;
}
ll phi(ll n)//欧拉
{ll ansn;for(ll i2;i*in;i)if(n%i0){ansans/i*(i-1);while(n%i0) n/i;}if(n1) ansans/n*(n-1);return ans;
}
ll power(ll x,ll b)//快速幂
{ll sum1;while(b){if(b1) summul(sum,x);xmul(x,x);b1;}return sum;
}
int main()
{while(scanf(%lld,L)L){L9*L/gcd(L,8LL);if(gcd(L,10LL)!1)//永远不可能{printf(Case %lld: 0\n,tot);continue;}ll ans(1LL63-1),aphi(L);//计算欧拉函数for(ll i1;i*ia;i)if(a%i0){if(power(10,i)1)//判断答案ansmin(ans,i);if(power(10,a/i)1)//判断答案ansmin(ans,a/i);}printf(Case %lld: %lld\n,tot,ans);}
}
