蓝桥杯2022年第十三届省赛真题-因数平方和(中)

Frommoon / 2024-03-01 / 原文

题目
法一、暴力枚举
法二、数学公式
法三、求逆元
- 乘法逆元

题目

法一、暴力枚举

一个f(n)有一个或多个约数，这一个或多个约数又是f(n)的倍数，直接统计i(从1到n)在f(1)...f(n)中出现了几次,这里可以归纳总结：每个i出现做为因子的个数是（n/i），最后全部取平方加起来则求到了题目要求的g(n),最后进行求余输出即可。
g(n)=（n/i）ii,其中i从1到n

mod = 1000000007
ans = 0
n = int(input())
for i in range(1, n+1):
    ans += ((n//i)*i*i) % mod #n//i表示i的个数，*了两次i表示平方，
    ans %= mod#ans 可能会累加大量的数值，进行取模运算，确保ans 的值不会超过机器的整数表示范围，导致计算结果不准确或溢出。
print(ans)

只能过30%的案例

法二、数学公式

上面我们得到了：g(n)=（n/i）ii,其中i从1到n

mod = 1000000007
am = 1000000007 * 6
ans = 0
# 输入n
n = int(input())
m = n
for i in range(1, n+1):
    #可以举例子发现g(n)=n // i的平方和
    m = n // i#每次计算1~m
    temp = (((m * (m + 1)) % am) * (2 * m + 1)) % am#计算1加到m的公式
    temp //= 6
    ans += temp
    ans %= mod
# 输出结果
print(ans)

法三、求逆元

乘法逆元

举个例子：（7/2）mod 5=>(7 * 1/2) mod 5=>(7 * 2^-1)mod 5;现在我们来找2的-1次方的逆元，就是找（多少2）mod 5=1,因为（23）mod 5=1，所以2和3在mod 5下互为“倒数”，这个倒数就叫乘法逆元。于是(7 * 2^-1)mod 5=>(7*3) mod 5=1。其中：乘法逆元只考虑取比mod 后数小的数；整数与模数互素才有乘法逆元。
未理解

mod = 1000000007
ni = 166666668#为mod的逆元
ans = 0

n = int(input())  # 输入n
m = n

# 第一个循环，从1到10000
for i in range(1, 10001):
    m = n // i  # 计算m
    if m == 0:
        print(ans)
        exit(0)
    temp = (((m * (m + 1)) % mod) * (2 * m + 1)) % mod  # 计算临时变量temp
    temp *= ni
    temp %= mod
    ans += temp
    ans %= mod

# 第二个循环，从10001到m
for i in range(1, m + 1):
    ans += (((n // i - 10000) * i) % mod) * i
    ans %= mod

print(ans)