102922: [Atcoder]ABC292 C - Four Variables

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：9 Solved：0

Description

Score : $300$ points

Problem Statement

You are given a positive integer $N$.
Find the number of quadruples of positive integers $(A,B,C,D)$ such that $AB + CD = N$.

Under the constraints of this problem, it can be proved that the answer is at most $9 \times 10^{18}$.

Constraints

  • $2 \leq N \leq 2 \times 10^5$
  • $N$ is an integer.

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the answer.

Sample Input 1

4

Sample Output 1

8

Here are the eight desired quadruples.

  • $(A,B,C,D)=(1,1,1,3)$
  • $(A,B,C,D)=(1,1,3,1)$
  • $(A,B,C,D)=(1,2,1,2)$
  • $(A,B,C,D)=(1,2,2,1)$
  • $(A,B,C,D)=(1,3,1,1)$
  • $(A,B,C,D)=(2,1,1,2)$
  • $(A,B,C,D)=(2,1,2,1)$
  • $(A,B,C,D)=(3,1,1,1)$

Sample Input 2

292

Sample Output 2

10886

Sample Input 3

19876

Sample Output 3

2219958

Input

题意翻译

### 题意简述 给定正整数 $N$，求**有序正整数**四元组 $(A,B,C,D)$ 的个数使得 $AB+CD=N$。 注：有序指**实质相同，但顺序不同的算不同的两个。**

Output

分数：300分

问题描述

给你一个正整数$N$。

找出所有满足$AB + CD = N$的正整数四元组$(A,B,C,D)$的个数。

在这个问题的约束下，可以证明答案最多为$9 \times 10^{18}$。

约束

  • $2 \leq N \leq 2 \times 10^5$
  • $N$为整数。

输入

输入从标准输入按以下格式给出：

$N$

输出

输出答案。

样例输入 1

4

样例输出 1

8

以下是八个满足条件的四元组。

  • $(A,B,C,D)=(1,1,1,3)$
  • $(A,B,C,D)=(1,1,3,1)$
  • $(A,B,C,D)=(1,2,1,2)$
  • $(A,B,C,D)=(1,2,2,1)$
  • $(A,B,C,D)=(1,3,1,1)$
  • $(A,B,C,D)=(2,1,1,2)$
  • $(A,B,C,D)=(2,1,2,1)$
  • $(A,B,C,D)=(3,1,1,1)$

样例输入 2

292

样例输出 2

10886

样例输入 3

19876

样例输出 3

2219958

HINT

求四个正整数a、b、c、d，凑出a*b + c*d = n的方案数是多少？

Source/Category

加入题单

上一题 下一题 算法标签：