3356. 解方程

单点时限: 2.0 sec

内存限制: 256 MB

简而言之,本题任务就是解方程。共有两个子任务。

子任务 1:小学生

作为小学生,我们只会解一元一次方程,一元一次方程最终都可以化为 $ax=n$ 的形式。现在问:对于给定的 $n$,要使得 $x$ 有正整数解,总共可以取多少个不同的 $a$ 呢?

子任务 2:中学生

作为中学生,我们只会解二元一次不定方程,二元一次不定方程最终都可以化为 $ax+by=n$ 的形式。现在问:对于给定的 $n$,要使得 $x,y$ 有正整数解,总共可以取多少对不同的 $(a,b)$ 呢?

输入格式

输出一行两个整数 $q,n$ $(q \in {1,2})$。

$q=1$ 表示你现在要解决小学生的情况,$q=2$ 表示你现在要解决中学生的情况。

数据规模约定(每个测试点占本题总分值的 $10\%$):

测试点 $q$ $n$
1 $=1$ $1 \leq n \leq 1~000$
2, 3 $=1$ $1 \leq n \leq 300~000$
4, 5 $=2$ $1 \leq n \leq 50$
6, 7 $=2$ $1 \leq n \leq 500$
8, 9 $=2$ $1 \leq n \leq 50~000$
10 $=2$ $1 \leq n \leq 300~000$

输出格式

输出一个整数,表示答案。

样例

Input
2 4
Output
6
Input
1 10
Output
4

提示

当 $q=1,n=10$ 时,$a$ 可以取 $1,2,5,10$。

当 $q=2, n=4$ 时,$(a,b)$ 可以取 $(1,1), (1,2), (1,3), (2,1), (2,2), (3,1)$。

98 人解决,321 人已尝试。

136 份提交通过,共有 1582 份提交。

5.7 EMB 奖励。

创建: 7 年,3 月前.

修改: 7 年,2 月前.

最后提交: 2 月,4 周前.

来源: 2017 直升研究生机试

题目标签