首页 > 试题广场 >

求root(N, k)

[编程题]求root(N, k)

热度指数：19461 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

N<k时，root(N,k) = N，否则，root(N,k) = root(N',k)。N'为N的k进制表示的各位数字之和。输入x,y,k，输出root(x^y,k)的值 (这里^为乘方，不是异或)，2=<k<=16，0<x,y<2000000000，有一半的测试点里 x^y 会溢出int的范围(>=2000000000)

输入描述:

    每组测试数据包括一行，x(0<x<2000000000), y(0<y<2000000000), k(2<=k<=16)

输出描述:

    输入可能有多组数据，对于每一组数据，root(x^y, k)的值

示例1

输入

4 4 10

输出

算法知识视频讲解

Python

把伤害当做酒窝

这个代码出现错误 RecursionError: maximum recursion depth exceeded in comparison
请问一下大神们，我编写的程序在算力允许的条件下是不是没有错？这个代码在数据不大
的时候能执行，太大了就出现以上错误了
def toStr(n, k):
    '''把n转换为k进制'''
    numbers = '0123456789ABCDEF'
    if n < k:
        return numbers[n]
    else:
        return toStr(n//k, k) + numbers[n % k]
def root(N, k):
    if N < k:
        return N
    else:
        str_N = str(toStr(N, k))
        return root(sum(int(i) for i in str_N), k)
x,y,z = map(int, input().split())
print(root(x**y, z))

发表于 2020-04-30 17:17:20 回复(0)

Python

TimeMac

1、模运算：（a * b）mod n = (（a mod n） b ) mod n

2、 N=a0+a1*k+a2*k^2+……+an*k^n;

N'=a0+a1+a2+……+an;

N-N'=a1*(k-1)+a2*(k^2-1)+……+an*(k^n-1);

提取(k-1)有: (N-N')%(K-1)=0;

继续递推下去有：（N-N'）%(k-1) =0；

try:
    while True:
        x,y,k = list(map(int,input().split()))
        result = 1
        while y:
            if y&1:
                result = (result*x)%(k-1)
            x = (x*x)%(k-1)
            y>>=1
        result = result if result else k-1
        print(result)
except Exception:
    pass

http://blog.sina.com.cn/s/blog_8619a25801010wcy.html

编辑于 2018-10-10 15:31:56 回复(0)