2014
01-26

# The Luckiest number

Chinese people think of ’8′ as the lucky digit. Bob also likes digit ’8′. Moreover, Bob has his own lucky number L. Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of L and consist of only digit ’8′.

The input consists of multiple test cases. Each test case contains exactly one line containing L(1 ≤ L ≤ 2,000,000,000).

The last test case is followed by a line containing a zero.

The input consists of multiple test cases. Each test case contains exactly one line containing L(1 ≤ L ≤ 2,000,000,000).

The last test case is followed by a line containing a zero.

8
11
16
0

Case 1: 1
Case 2: 2
Case 3: 0

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

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

#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) {// a * b % 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) { //a ^ b % c 改成mod_pow就不行，中间发生了溢出，还是这个模板靠谱
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) {//如果和10不互素
puts("0");//则答案不存在
return;
}
phi = getPhi(c);
findpFactor(phi);
len_factor = 0;
dfs(0, 1);//得到所有phi的因子相乘小于等于phi的乘积
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;
}
}
}
#include <iostream>
using namespace std;
int main() {
int n, cas;
mkprime();
cas = 0;
while (~scanf("%d", &n) && n) {
printf("Case %d: ", ++cas);
solve(n);
}
return 0;
}

1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c