D. A Creative Cutout

Codeforces

IDCF933D

Time2000ms

Memory256MB

Difficulty—

brute forcecombinatoricsmath

English · Original

Chinese · Translation

Formal · Original

_Everything red frightens Nian the monster. So do red paper and... you, red on Codeforces, potential or real._ Big Banban has got a piece of paper with endless lattice points, where lattice points form squares with the same area. His most favorite closed shape is the circle because of its beauty and simplicity. Once he had obtained this piece of paper, he prepares it for paper-cutting. <center>![image](https://espresso.codeforces.com/82edc897487bb94b56952d372bcbcb46bd964bb6.png)</center>He drew _n_ concentric circles on it and numbered these circles from 1 to _n_ such that the center of each circle is the same lattice point and the radius of the _k_\-th circle is times the length of a lattice edge. Define the degree of beauty of a lattice point as the summation of the **indices** of circles such that this lattice point is inside them, or on their bounds. Banban wanted to ask you the total degree of beauty of all the lattice points, but changed his mind. Defining the total degree of beauty of all the lattice points on a piece of paper with _n_ circles as _f_(_n_), you are asked to figure out . ## Input The first line contains one integer _m_ (1 ≤ _m_ ≤ 1012). ## Output In the first line print one integer representing . [samples] ## Note A piece of paper with 5 circles is shown in the following. <center>![image](https://espresso.codeforces.com/b63097ed9dc567853f8c13b2a90317a6ad36bb91.png)</center>There are 5 types of lattice points where the degree of beauty of each red point is 1 + 2 + 3 + 4 + 5 = 15, the degree of beauty of each orange point is 2 + 3 + 4 + 5 = 14, the degree of beauty of each green point is 4 + 5 = 9, the degree of beauty of each blue point is 5 and the degree of beauty of each gray point is 0. Therefore, _f_(5) = 5·15 + 4·14 + 4·9 + 8·5 = 207. Similarly, _f_(1) = 5, _f_(2) = 23, _f_(3) = 50, _f_(4) = 102 and consequently .

_一切红色的事物都让年兽害怕。红色的纸张，以及你——在 Codeforces 上红色的你，无论是潜在的还是真实的，都令它恐惧。_ Big Banban 得到一张拥有无限格点的纸，格点构成面积相等的正方形。他最喜爱的封闭图形是圆，因为它的美丽与简洁。一旦得到这张纸，他就准备进行剪纸。他在纸上画了 #cf_span[n] 个同心圆，并将这些圆从 #cf_span[1] 到 #cf_span[n] 编号，使得每个圆的圆心都是同一个格点，且第 #cf_span[k] 个圆的半径是格点边长的 #cf_span[k] 倍。定义一个格点的“美丽度”为所有包含该格点（包括边界）的圆的编号之和。Banban 原本想问你所有格点的总美丽度，但他改变了主意。定义在拥有 #cf_span[n] 个圆的纸上，所有格点的总美丽度为 #cf_span[f(n)]，你需要计算。第一行包含一个整数 #cf_span[m] #cf_span[(1 ≤ m ≤ 10^{12})]。在第一行输出一个整数，表示。一张带有 #cf_span[5] 个圆的纸如下所示。共有 #cf_span[5] 种类型的格点：每个红色格点的美丽度为 #cf_span[1 + 2 + 3 + 4 + 5 = 15]，每个橙色格点的美丽度为 #cf_span[2 + 3 + 4 + 5 = 14]，每个绿色格点的美丽度为 #cf_span[4 + 5 = 9]，每个蓝色格点的美丽度为 #cf_span[5]，每个灰色格点的美丽度为 #cf_span[0]。因此，#cf_span[f(5) = 5·15 + 4·14 + 4·9 + 8·5 = 207]。类似地，#cf_span[f(1) = 5, f(2) = 23, f(3) = 50, f(4) = 102]，因此。 ## Input 第一行包含一个整数 #cf_span[m] #cf_span[(1 ≤ m ≤ 10^{12})]。 ## Output 在第一行输出一个整数，表示。 [samples] ## Note 一张带有 #cf_span[5] 个圆的纸如下所示。共有 #cf_span[5] 种类型的格点：每个红色格点的美丽度为 #cf_span[1 + 2 + 3 + 4 + 5 = 15]，每个橙色格点的美丽度为 #cf_span[2 + 3 + 4 + 5 = 14]，每个绿色格点的美丽度为 #cf_span[4 + 5 = 9]，每个蓝色格点的美丽度为 #cf_span[5]，每个灰色格点的美丽度为 #cf_span[0]。因此，#cf_span[f(5) = 5·15 + 4·14 + 4·9 + 8·5 = 207]。类似地，#cf_span[f(1) = 5, f(2) = 23, f(3) = 50, f(4) = 102]，因此。

**Definitions** Let $ n \in \mathbb{Z}^+ $. For each $ k \in \{1, \dots, n\} $, let $ C_k $ be the circle centered at the origin with radius $ k $. Let $ \mathbb{Z}^2 $ denote the set of all lattice points in the plane. For a lattice point $ p \in \mathbb{Z}^2 $, define its *beauty degree* as: $$ b(p) = \sum_{\substack{k=1 \\ p \in C_k}}^n k $$ Define the total beauty function: $$ f(n) = \sum_{p \in \mathbb{Z}^2} b(p) $$ **Constraints** Given $ m \in \mathbb{Z} $ with $ 1 \leq m \leq 10^{12} $. **Objective** Compute $ f(m) $.

Samples

Input #1

Output #1

Input #2

Output #2

788243189

API Response (JSON)

{
  "problem": {
    "name": "D. A Creative Cutout",
    "description": {
      "content": "_Everything red frightens Nian the monster. So do red paper and... you, red on Codeforces, potential or real._ Big Banban has got a piece of paper with endless lattice points, where lattice points fo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF933D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Everything red frightens Nian the monster. So do red paper and... you, red on Codeforces, potential or real._\n\nBig Banban has got a piece of paper with endless lattice points, where lattice points fo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "_一切红色的事物都让年兽害怕。红色的纸张，以及你——在 Codeforces 上红色的你，无论是潜在的还是真实的，都令它恐惧。_\n\nBig Banban 得到一张拥有无限格点的纸，格点构成面积相等的正方形。他最喜爱的封闭图形是圆，因为它的美丽与简洁。一旦得到这张纸，他就准备进行剪纸。\n\n他在纸上画了 #cf_span[n] 个同心圆，并将这些圆从 #cf_span[1] 到 #cf_span[n]...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $. For each $ k \\in \\{1, \\dots, n\\} $, let $ C_k $ be the circle centered at the origin with radius $ k $.  \nLet $ \\mathbb{Z}^2 $ denote the set of all latti...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments