Chinaunix首页 | 论坛 | 博客
  • 博客访问: 739959
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1115
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,既当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2017-06-05 15:28:23

题目描述

路人甲给你出了一道奇怪的问题,他给你了一个正整数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


实现

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<stdlib.h>

  4. #define llong long long

  5. static llong power(long key, int n)
  6. {
  7.     int i;
  8.     llong ret = 1;
  9.     for (i = 0; i < n; i++)
  10.         ret *= key;
  11.     return ret;
  12. }

  13. static void printKS(int base, int len)
  14. {
  15.     int hashLen;
  16.     short* rcd;
  17.     int cur = 1;
  18.     int carry = base;
  19.     
  20.     if (base < 100 || base >= 10000 || len < 0 || len > 4)
  21.     {
  22.         printf("invaild input\n");
  23.         return;
  24.     }
  25.      hashLen = power(10,len);
  26.     rcd = (short*)calloc(sizeof(short), hashLen + 1);
  27.     if (!rcd)
  28.         return;

  29.     while(carry < hashLen)
  30.     {
  31.         carry *= base;
  32.         cur++;        
  33.     }

  34.     carry = carry % hashLen;
  35.     rcd[carry] = cur;

  36.     while (cur <= hashLen)
  37.     {
  38.         cur++;
  39.         carry = (carry * base) % hashLen;
  40.         if (rcd[carry] > 0)
  41.         {
  42.             printf("%d, %d\n", cur, rcd[carry]);
  43.             return;
  44.         }
  45.         else
  46.         {
  47.             rcd[carry] = cur;
  48.         }
  49.     }
  50. }

  51. int main(int argc, char** argv)
  52. {
  53.     int base;
  54.     int len;

  55.     scanf("%d %d", &base, &len);
  56.     printf("--%d %d\n", base, len);
  57.     printKS(base, len);
  58.     return 0;
  59. }


阅读(2340) | 评论(0) | 转发(0) |
0

上一篇:lua math 库

下一篇:【RQNOJ】PID4 / 数列

给主人留下些什么吧!~~