混乘数字

问题描述

混乘数字的定义如下: 对于一个正整数 n，如果存在正整数 a,b，使得 n=a×b，而且 a 和 b 的十进制数位中每个数字出现的次数之和与 n 中对应数字出现次数相同，则称 n 为混乘数字。

例如，对于正整数 n=126，存在 a=6，b=21 满足条件，因此 126 是一个混乘数字。

又如，对于正整数 n=180225，存在 a=225, b=801 满足条件，因此 180225 是一个混乘数字。

请你帮助计算出，1∼1000000 (含)之间一共有多少个数字是混乘数字。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	5s	256M
PyPy3	5s	256M
Go	5s	256M
JavaScript	5s	256M

来自: 2.混乘数字 – 蓝桥云课

我的题解

以下是原始代码

from collections import Counter
import math


# 将两个字典的值相加，返回一个新的排序字典（键为字符串，值为整数）
def add_dict(dic_1, dic_2):
    result = dic_1.copy()
    for key, value in dic_2.items():
        if key in result:
            result[key] += value
        else:
            result[key] = value
    sorted_result = dict(sorted(result.items()))
    return sorted_result


# 检查给定的数是否可以被两个数字整除，且这两个数字的各个数位可以刚好组成被检查的数
def find_factor(num):
    dic_0 = dict(Counter(str(num)))
    sorted_dic_0 = sorted(dic_0.items())
    for i in range(2, math.isqrt(num) + 1):
        if num % i == 0:
            dic_1 = dict(Counter(str(i)))
            sorted_dic_1 = dict(sorted(dic_1.items()))
            dic_2 = dict(Counter(str(num // i)))
            sorted_dic_2 = dict(sorted(dic_2.items()))
            if dict(sorted_dic_0) == add_dict(sorted_dic_1, sorted_dic_2):
                return True
    return False


# 主程序：计算满足条件的数的个数，并打印结果
if __name__ == '__main__':
    count = 0
    for i in range(1, 1000000 + 1):
        if find_factor(i):
            count += 1
    print(count)

由于数据量有点大，运行时间很长。

输出结果是：590

AI 在原始代码基础上进行优化，以下是优化后的代码（性能略微提升）：

from collections import Counter
import math


# 将两个字典的值相加，返回一个新的排序字典（键为字符串，值为整数）
def add_dict(dic_1, dic_2):
    result = dic_1.copy()
    for key, value in dic_2.items():
        if key in result:
            result[key] += value
        else:
            result[key] = value
    sorted_result = dict(sorted(result.items()))
    return sorted_result


# 检查给定的数是否可以被两个数字整除，且这两个数字的各个数位可以刚好组成被检查的数
def find_factor(num):
    dic_0 = dict(Counter(str(num)))
    sorted_dic_0 = sorted(dic_0.items())
    for i in range(2, math.isqrt(num) + 1):
        if num % i == 0:
            dic_1 = dict(Counter(str(i)))
            sorted_dic_1 = dict(sorted(dic_1.items()))
            dic_2 = dict(Counter(str(num // i)))
            sorted_dic_2 = dict(sorted(dic_2.items()))
            if dict(sorted_dic_0) == add_dict(sorted_dic_1, sorted_dic_2):
                return True
    return False


# 主程序：计算满足条件的数的个数，并打印结果
if __name__ == '__main__':
    count = 0
    for i in range(1, 1000000 + 1):
        if find_factor(i):
            count += 1
    print(count)

---

存档地址：https://www.yuque.com/worthstudy/study/iodybypnpmpg2yne?singleDoc# 《混乘数字》