个人简介
小公司研发总监，既当司令也当兵！
文章分类
相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： linux
2017-06-05 15:28:23
题目描述
路人甲给你出了一道奇怪的问题，他给你了一个正整数l，他想知道当正整数m,n为何值时，l^m与l^n的最后k位数字相同。
路人甲考虑到可能会有很多组解，你只需要告诉他最小的m，n且0
分析：
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;
- }
给主人留下些什么吧！~~