学步园

题目思路：

求解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<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#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<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#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<stdio.h>
#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;
}