丝路带分数

2026 青少年信息素养大赛 复赛卷五 · 初中组 C++ 第 11 题

题目描述

古代丝绸之路的商队在记录货物总重量时，常将一个整数总重量 N 表示为带分数形式 N = a + b/c，其中：

• a, b, c 为正整数
• 数字 1~9（不含 0）在 a, b, c 中必须出现，且只能出现一次
• b 必须能被 c 整除
• a + b/c = N

例如：100 = 3 + 69258/714，其中 1~9 每个数字各出现一次。100 共有 11 种合法的表示方式。

请编写一个程序，根据输入的正整数 N，输出该数字用数码 1~9 不重复、不遗漏地组成带分数表示的全部可能性数量。

输入格式

输入一行，包含一个正整数 N（1 ≤ N < 1000000）。

输出格式

输出一行，一个整数，表示有多少种分法。

样例输入

100

样例输出

11

数据范围

1 ≤ N < 1000000