******D

Luogu
IDLGP9817
Time1000ms
Memory128MB
DifficultyP5
O2优化
定义一个长度为 $m$ 的非空序列 $p_1,p_2,...,p_m$ 是**乱**的当且仅当满足以下两个条件。 - 所有元素之和不超过 $n$,即 $\sum_{i=1}^m p_i\le n$。 - 对于任意一个元素 $p_i$ 满足 $p_i=1$ 或 $p_i$ 为质数。 定义一个**乱**的序列 $p_1,p_2,...,p_m$ 的**乱斗值**为该序列中所有元素减 $k$ 的平方和,即 $\sum_{i=1}^m (p_i-k)^2$。 特别的,定义一个**不乱**的序列的乱斗值为 $0$。 现在给定两个正整数 $n,k$,问所有序列中**乱斗值**最大的序列的**乱斗值**是多少。 ## Input 本题有多组测试数据。第一行输入一个正整数 $T$,表示测试数据组数,接下来分别输入 $T$ 组数据。 对于每组测试数据,输入一行两个正整数 $n,k$。 ## Output 对于每组测试数据输出一行一个整数表示答案。 [samples] ## Background 欢迎新斗友@[lmxcslD](https://www.luogu.com.cn/user/358957) ## Note #### 样例解释 对于样例第 $1,2,3,4$ 组数据,其中一种**乱斗值**最大的序列分别为 $(1),(2),(1,3),(5)$。 #### 数据范围与约定 |测试点编号|$T$|$n$|$k$|特殊性质| |:-:|:-:|:-:|:-:|:-:| |$1$|$=100$|$\le 10$|$\le 10$|无| |$2$|$=200$|$\le 30$|$\le 10$|无| |$3$|$=300$|$\le 10^3$|$\le 5\times 10^4$|无| |$4$|$=400$|$\le 10^5$|$\le 5\times 10^4$|无| |$5$|$=500$|$\le 10^7$|$\le 5\times 10^4$|无| |$6$|$=600$|$\le 10^9$|$=1$|$n$ 为质数| |$7$|$=700$|$\le 10^9$|$=1$|无| |$8$|$=800$|$\le 10^9$|$=44444$|无| |$9$|$=900$|$\le 10^9$|$\le 5\times 10^4$|$n$ 为质数| |$10$|$=10^3$|$\le 10^9$|$\le 5\times 10^4$|无| 对于所有测试点,保证 $1\le T\le 10^3$,$1\le n\le 10^9$,$1\le k\le 5\times 10^4$。
Samples
Input #1
5
1 1
2 1
4 1
5 2
10 10
Output #1
0
1
4
9
810
API Response (JSON)
{
  "problem": {
    "name": "******D",
    "description": {
      "content": "定义一个长度为 $m$ 的非空序列 $p_1,p_2,...,p_m$ 是**乱**的当且仅当满足以下两个条件。 - 所有元素之和不超过 $n$,即 $\\sum_{i=1}^m p_i\\le n$。 - 对于任意一个元素 $p_i$ 满足 $p_i=1$ 或 $p_i$ 为质数。 定义一个**乱**的序列 $p_1,p_2,...,p_m$ 的**乱斗值**为该序列中所有元素减 $k$ 的平方",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9817"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "定义一个长度为 $m$ 的非空序列 $p_1,p_2,...,p_m$ 是**乱**的当且仅当满足以下两个条件。\n\n- 所有元素之和不超过 $n$,即 $\\sum_{i=1}^m p_i\\le n$。\n- 对于任意一个元素 $p_i$ 满足 $p_i=1$ 或 $p_i$ 为质数。\n\n定义一个**乱**的序列 $p_1,p_2,...,p_m$ 的**乱斗值**为该序列中所有元素减 $k$ 的平方...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments