欧拉定理的应用

一个小技巧,连续 \(x\) 个 \(8\) 组成的数可以表示为 \(8 *(10^x - 1) /9\)

题目要求就变成了求满足 \(L \mid 8 * (10^x - 1) /9\)的最小的x

将原式整理可得:

\[L*9/gcd(L, 8) \mid 10 ^ x -1\]

设 \(p = L * 9/gcd(L,8)\)

原式可化为: \(10^x \equiv 1 \pmod p\)

引理:

满足上式的最小的 \(x\) 是\(\varphi( p)\)的约数

可用数学归纳法证明,即设 \(p = x * k + r\)证明

枚举\(\varphi (p)\)的约数,用快速幂验证即可

]注意本题的数据范围很大,有时会出现两个long long 相乘,所以要用慢速乘

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define ll long long using namespace std;ll num[75000], tot;ll gcd(ll a, ll b) {    return b ? gcd(b, a % b) : a;}ll phi(ll n) {    ll ans = n;    for(ll i = 2 ; i * i<= n ; i++) {        if(n % i == 0) {            ans = ans / i * (i - 1);            while(n % i == 0) n /= i;        }    }    if(n > 1) ans = ans /n * (n - 1);    return ans;}ll mul(ll a, ll b, ll p){    ll ans = 0ll;    while(b) {        if(b & 1ll) (ans +=  a) %= p;        (a += a) %= p;        b >>= 1;    }    return ans;}ll quick_mod(ll a, ll n, ll p) {    ll ans = 1ll;    while(n) {        if(n & 1ll) ans = mul(ans, a, p);        a = mul(a, a, p);        n >>= 1;    }    return ans;}ll work(ll n, ll p) {    //ll ans = 0x3f7f7f7f7f7f7f7f;    tot = 0;    for(ll i = 1ll ; i * i <= n ; i++) {        if(n % i == 0){            if(quick_mod(10, i, p) == 1ll) return i;            if((n / i) != i) {                num[++tot] = n / i;            }        }    }    for(int i = tot; i >= 1; i--) {        if(quick_mod(10, num[i], p) == 1ll) return num[i];    }    return n;}int main() {    for(int k = 1 ;  ; k++) {        ll n ;        cin>>n;        if(!n) break;        ll d = gcd(n, 8ll);        ll t = 9 * n / d;        if(gcd(t, 10) != 1) {printf("Case %d: 0\n", k);}        else printf("Case %d: %lld\n", k, work(phi(t), t));    }    return 0;}