题目思路：

求解10^x = 1 (mod 9*L/gcd(L,8))的满足x>0的最小解就是答案

由8构成的数A设有x位

那么A=8(10^0+10^1+...+10^(x-1));

很容易得到A=(8/9)*(10^x-1);

题目的要求就是A=0(mod L)

就是(8/9)*(10^x-1)=0(mod L);

->8*(10^x-1)=0(mod 9L);

->10^x-1=0(mod 9L/gcd(L,8));

->10^x =1 (mod 9L/gcd(L,8));

令p=9*L/gcd(L,i), 等价于10^x==1(mod p),求满足条件的最小的整数x

看到这个式子，我们的第一反应就是数论书上的Euler定理，但是如果gcd（10，p)!=1,即不互素，也就是不满足欧拉定理的条件了，所以此时为no answer.

if(gcd（10，p)==1) 满足欧拉定理, 我们知道10^oula(p)==1(mod p)肯定是满足的;

虽然oula(p)满足上述同余方程，但题目求是最小x，而oula(p)未必是最小的解。考虑到oula(p)不是素数，所以我们就要将oula(p)因子分解，求出oula(p)所有的因子，然后逐个从小到大枚举，如果满足10^x==1(mod p) (其中x为oula(p)的因子)，x即为答案。

 

#include
      
        #include
       
         #include
        
          #include
         
           #define LL long long #define nmax 134165 #define nnum 13000 #define num8 8 #define num9 9 #define num10 10 int flag[nmax], prime[nnum], cpfactor[nnum]; LL pfactor[nnum], factor[nnum]; int plen, len_pfactor, len_factor; void mkprime() {
    int i, j;     memset(flag, -1, sizeof(flag)); for (i = 2, plen = 0; i < nmax; i++) {
    if (flag[i]) {
                prime[plen++] = i;         } for (j = 0; (j < plen) && (i * prime[j] < nmax); j++) {
                flag[i * prime[j]] = 0; if (i % prime[j] == 0) {
    break;             }         }     } } int cmp(const void *a, const void *b) {
        LL temp = *(LL *) a - *(LL *) b; if (temp > 0) {
    return 1;     } else if (temp < 0) {
    return -1;     } return 0; } LL getPhi(LL n) {
    int i, te;     LL phi;     te = (int) sqrt(n * 1.0); for (i = 0, phi = n; (i < plen) && (prime[i] <= te); i++) {
    if (n % prime[i] == 0) {
                phi = phi / prime[i] * (prime[i] - 1); while (n % prime[i] == 0) {
                    n /= prime[i];             }         }     } if (n > 1) {
            phi = phi / n * (n - 1);     } return phi; } LL modular_multi(LL a, LL b, LL c) {
        LL res, temp;     res = 0, temp = a % c; while (b) {
    if (b & 1) {
                res += temp; if (res >= c) {
                    res -= c;             }         }         temp <<= 1; if (temp >= c) {
                temp -= c;         }         b >>= 1;     } return res; } LL modular_exp(LL a, LL b, LL c) {
        LL res, temp;     res = 1 % c, temp = a % c; while (b) {
    if (b & 1) {
                res = modular_multi(res, temp, c);         }         temp = modular_multi(temp, temp, c);         b >>= 1;     } return res; } LL gcd(LL a, LL b) {
    if (a < b) {
            a ^= b, b ^= a, a ^= b;     } if (b == 0) {
    return a;     } if (!(a & 1) && !(b & 1)) return gcd(a >> 1, b >> 1) << 1; else if (!(b & 1)) return gcd(a, b >> 1); else if (!(a & 1)) return gcd(a >> 1, b); else return gcd(b, a - b); } void findpFactor(LL n) {
    int i, te, cnt;     te = (int) sqrt(n * 1.0); for (i = 0, len_pfactor = 0; (i < plen) && (prime[i] <= te); i++) {
    if (n % prime[i] == 0) {
                cnt = 0; while (n % prime[i] == 0) {
                    cnt++;                 n /= prime[i];             }             pfactor[len_pfactor] = prime[i];             cpfactor[len_pfactor++] = cnt;         }     } if (n > 1) {
            pfactor[len_pfactor] = n;         cpfactor[len_pfactor++] = 1;     } } void dfs(int k, LL now) {
    if (k == len_pfactor) {
            factor[len_factor++] = now; return;     } int i; for (i = 0; i < cpfactor[k]; i++) {
            now = now * pfactor[k];         dfs(k + 1, now);     } for (i = 0; i < cpfactor[k]; i++) {
            now = now / pfactor[k];     }     dfs(k + 1, now); } void solve(int n) {
    int i, d;     LL c, phi;     d = gcd(n, num8);     c = (LL) n;     c = c / d * num9; if (gcd(num10, c) != 1) {
            puts("0"); return;     }     phi = getPhi(c);     findpFactor(phi);     len_factor = 0;     dfs(0, 1);     qsort(factor, len_factor, sizeof(factor[0]), cmp); for (i = 0; i < len_factor; i++) {
    if (modular_exp(num10, factor[i], c) == 1) {
                printf("%I64d\n", factor[i]); return;         }     } } int main() {
    #ifndef ONLINE_JUDGE     freopen("data.in", "r", stdin); #endif int n, cas;     mkprime();     cas = 0; while (~scanf("%d", &n), n) {
            printf("Case %d: ", ++cas);         solve(n);     } return 0; }
         
        
       
      

另一种思路：

 

/*  * hdu2462.c  *  *  Created on: 2011-9-9  *      Author: bjfuwangzhu */ #include
     
       #include
      
        #include
       
         #include
        
          #define LL long long #define nmax 134165 #define nnum 12510 int flag[nmax], prime[nnum]; LL factor[nnum], cfactor[nnum], num[nnum]; int plen, nlen, flen; void init() {
        memset(flag, -1, sizeof(flag)); int i, j; for (i = 2, plen = 0; i < nmax; i++) {
    if (flag[i]) {
                prime[plen++] = i;         } for (j = 0; (j < plen) && (i * prime[j] < nmax); j++) {
                flag[i * prime[j]] = 0; if (i % prime[j] == 0) {
    break;             }         }     } } LL gcd(LL a, LL b) {
    if (a < b) {
            a ^= b, b ^= a, a ^= b;     } if (b == 0) {
    return a;     } if ((!(a & 1)) && (!(b & 1))) {
    return gcd(a >> 1, b >> 1) << 1;     } if (!(a & 1)) {
    return gcd(a >> 1, b);     } if (!(b & 1)) {
    return gcd(a, b >> 1);     } return gcd(a - b, b); } LL phi(LL n) {
    int temp, i;     LL pphi;     temp = (int) (sqrt(n * 1.0)); for (i = 0, pphi = n; (i < plen) && (prime[i] <= temp); i++) {
    if (n % prime[i] == 0) {
                pphi = pphi / prime[i] * (prime[i] - 1); while (n % prime[i] == 0) {
                    n /= prime[i];             }         }     } if (n > 1) {
            pphi = pphi / n * (n - 1);     } return pphi; } LL modular_mul(LL a, LL b, LL c) {
        LL res;     res = 0, a %= c; while (b) {
    if (b & 1) {
                res += a; if (res >= c) {
                    res -= c;             }         }         a <<= 1; if (a >= c) {
                a -= c;         }         b >>= 1;     } return res; } LL modular_exp(LL a, LL b, LL c) {
        LL res;     res = 1 % c, a %= c; while (b) {
    if (b & 1) {
                res = modular_mul(res, a, c);         }         a = modular_mul(a, a, c);         b >>= 1;     } return res; } void findFactor(LL n) {
    int i, te, cnt;     te = (int) (sqrt(n * 1.0)); for (i = 0, flen = 0; (i < plen) && (prime[i] <= te); i++) {
    if (n % prime[i] == 0) {
                cnt = 0; while (n % prime[i] == 0) {
                    cnt++;                 n /= prime[i];             }             cfactor[flen] = cnt;             factor[flen++] = prime[i];         }     } if (n > 1) {
            cfactor[flen] = 1;         factor[flen++] = n;     } } void bfs(int k, LL now, LL n) {
    if (k == flen) {
            num[nlen++] = now; return;     } int i; for (i = 0; i < cfactor[k]; i++) {
            now *= factor[k];         bfs(k + 1, now, n);     } for (i = 0; i < cfactor[k]; i++) {
            now /= factor[k];     }     bfs(k + 1, now, n); } int cmp(const void *a, const void *b) {
        LL n = *(LL *) a;     LL m = *(LL *) b;     LL temp;     temp = n - m; if (temp > 0) {
    return 1;     } if (temp < 0) {
    return -1;     } return 0; } void solve(LL n) {
        LL nphi;     nphi = phi(n);     findFactor(nphi);     nlen = 0;     bfs(0, 1, nphi);     qsort(num, nlen, sizeof(num[0]), cmp); int i; for (i = 0; i < nlen; i++) {
    if (modular_exp(10, num[i], n) == 1) {
                printf("%I64d\n", num[i]); return;         }     } } int main() {
    #ifndef ONLINE_JUDGE     freopen("data.in", "r", stdin); #endif     init(); int cas;     LL n;     cas = 0; while (scanf("%I64d", &n) != EOF,n) {
            cas++; if (n == 1) {
                printf("Case %d: 1\n", cas); continue;         } if (n % 16 == 0 || n % 5 == 0) {
                printf("Case %d: 0\n", cas); continue;         }         n = n / gcd(n, 8) * 9;         printf("Case %d: ", cas);         solve(n);     } return 0; }
        
       
      
     

 

 

/*  * fzu1017.c  *  *  Created on: 2011-9-9  *      Author: bjfuwangzhu */ #include
     
       #define nnum 10 void solve(int k) {
    int i, j, res; for (i = 1; i < nnum; i++) {
    for (j = 1, res = 0; j <= k; j++) {
                res = (res * 10 + i) % k; if (res == 0) {
                    printf("%d %d\n", i, j); return;             }         }     }     puts("-1"); } int main() {
    #ifndef ONLINE_JUDGE     freopen("data.in", "r", stdin); #endif int k; while (scanf("%d", &k) != EOF) {
            solve(k);     } return 0; }