首页 > 试题广场 >

求幂

[编程题]求幂

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

东东对幂运算很感兴趣,在学习的过程中东东发现了一些有趣的性质: 9^3 = 27^2, 2^10 = 32^2
东东对这个性质充满了好奇,东东现在给出一个整数n,希望你能帮助他求出满足 a^b = c^d(1 ≤ a,b,c,d ≤ n)的式子有多少个。
例如当n = 2: 1^1=1^1
1^1=1^2
1^2=1^1
1^2=1^2
2^1=2^1
2^2=2^2
一共有6个满足要求的式子

输入描述:

输入包括一个整数n(1 ≤ n ≤ 10^6)

输出描述:

输出一个整数,表示满足要求的式子个数。因为答案可能很大,输出对1000000007求模的结果

示例1

输入

输出

算法知识视频讲解

Python

谁能给我个offer啊6666

def count_expressions(n):
    # 创建一个字典来存储每个幂的结果及其对应的指数对
    powers = {}

    # 计算所有可能的 a^b 并存储在字典中
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            power = a ** b
            if power not in powers:
                powers[power] = []
            powers[power].append((a, b))

    # 计算所有可能的 c^d 并与 a^b 的结果进行比较
    count = 0
    for c in range(1, n + 1):
        for d in range(1, n + 1):
            power = c ** d
            if power in powers:
                count += len(powers[power])

    return count

发表于 2025-03-29 16:19:59 回复(0)