首页 > ACM题库 > HDU-杭电 > hdu 2462 The Luckiest number-数论-[解题报告]C++
2014
01-26

hdu 2462 The Luckiest number-数论-[解题报告]C++

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

题目思路:
求解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) {// 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;
}

解题转自:http://blog.csdn.net/julyana_lin/article/details/7983107


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