【RQNOJ】PID729 / 相同的后K位

题目描述

路人甲给你出了一道奇怪的问题，他给你了一个正整数L，他想知道当正整数m,n为何值时，L^m与L^n的最后K位数字相同。

路人甲考虑到可能会有很多组解，你只需要告诉他最小的m，n且0 为了降低难度，我们约定： 100<=L<=9999  并且 1<=k<=4

分析：

1.“L^m与L^n的最后K位数字相同”等价于：
(L^m)%(10^k) ==  (L^n)%(10^k), 其中m~=n

2. 考虑到m稍大时，（L^m）将会是一个非常大的数，会导致大数溢出，那么遍历（L^m）将不现实。

3. 假设，L%M=C，那么一定存在整数t使得：L = t*M + C
从而有： 
        (L*N)%M = ((t*M + C)*N) %M = (t*N*M)%M + (C*N)%M = (C*N)%M
即： (L*N)%M =  (C*N)%M

记 f(n) = (L^m)%M, 结合上面分析，我们可以得到：
f(n) = L %M (n =1)
f(n) = (f(n-1) * L) %M (n >=2)
对于任意正整数n， f(n) < M恒成立

按照题目描述，M=10^k, 对于有界的k，那么M是有界的。又由于 f(n) < M恒成立，即f(n)的值域为 [0,M-1], 可以推出当n取值为[1,M + 1]时，对应的f(n)至少有一组重复。

用数组S[M+1]记录f(n)的遍历情况（1到M+1）：
1）初始化S[i] = 0
2)  对于任意n，如果S[f(n)] ~= 0，那么说明存在i < n, 并且 f(i) == f(n)，遍历结束，i和n即我们需要的答案；否则记录S[f(n)] = n

实现

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define llong long long

static llong power(long key, int n)
{
    int i;
    llong ret = 1;
    for (i = 0; i < n; i++)
        ret *= key;
    return ret;
}

static void printKS(int base, int len)
{
    int hashLen;
    short* rcd;
    int cur = 1;
    int carry = base;

    if (base < 100 || base >= 10000 || len < 0 || len > 4)
    {
        printf("invaild input\n");
        return;
    }
     hashLen = power(10,len);
    rcd = (short*)calloc(sizeof(short), hashLen + 1);
    if (!rcd)
        return;

    while(carry < hashLen)
    {
        carry *= base;
        cur++;
    }

    carry = carry % hashLen;
    rcd[carry] = cur;

    while (cur <= hashLen)
    {
        cur++;
        carry = (carry * base) % hashLen;
        if (rcd[carry] > 0)
        {
            printf("%d, %d\n", cur, rcd[carry]);
            return;
        }
        else
        {
            rcd[carry] = cur;
        }
    }
}

int main(int argc, char** argv)
{
    int base;
    int len;

    scanf("%d %d", &base, &len);
    printf("--%d %d\n", base, len);
    printKS(base, len);
    return 0;
}