【全球新要闻】A. Greatest Convex【Codeforces Round #842 (Div. 2)】

2023-01-06 12:12:15 来源：博客园

A. Greatest Convex

You are given an integer \(k\). Find the largest integer \(x\), where \(1≤x

† \(y!\) denotes the factorial of \(y\), which is defined recursively as \(y!=y⋅(y−1)!\) for \(y≥1\) with the base case of \(0!=1\). For example, \(5!=5⋅4⋅3⋅2⋅1⋅0!=120\).

‡ If \(a\) and \(b\) are integers, then \(a\) is \(a\) multiple of \(b\) if there exists an integer \(c\) such that \(a=b⋅c\). For example, \(10\) is a multiple of \(5\) but \(9\) is not a multiple of \(6\).

(相关资料图)

InputThe first line contains a single integer \(t\) \((1≤t≤10^4)\) — the number of test cases. The description of test cases follows.

The only line of each test case contains a single integer \(k\) \((2≤k≤10^9)\).

OutputFor each test case output a single integer — the largest possible integer \(x\) that satisfies the conditions above.

If no such \(x\) exists, output \(−1\).

Exampleinput

436810

output

2579

NoteIn the first test case, \(2!+1!=2+1=3\), which is a multiple of \(3\).

In the third test case, \(7!+6!=5040+720=5760\), which is a multiple of \(8\).

原题链接

简述题意

给出\(t\)个\(k\)，找出是否存在一个\(x\)满足\(1≤x

思路

由于\(k\)的范围是\((2≤k≤10^9)\)，因此不能直接枚举求阶乘
观察example的input和output数据的特性我们可以猜测总是存在最大的\(x\)使得\(x = k - 1\)满足条件
当\(x = k - 1\)时\(x! + (x − 1)! = (x + 1) * (x - 1)! = k * (k - 2)!\)总是满足是k的倍数

代码

点击查看代码

#includeusing namespace std;int k,t;int main(){cin >> t;while(t -- ){cin >> k;cout << k - 1 << endl;}}

解题历程

错误方向浪费大量时间：多种方式求阶乘，分解质因数，二分搜索
Runtime error on pretest 2(218 ms,262100 KB)【00:19】//阶乘
Wrong answer on pretest 1(0 ms,3900 KB)【00:45】//分解质因数
Compilation error(0 ms,0 KB)【00:55】//看出规律，蒙出答案k-1
AC(46 ms,0 KB)【00:57】

经验总结

仔细思考数据范围与关系式的关系
签到题就会有签到题的样子：代码量小，如果代码量大了一个认真分析是否方向错误
可以看排名中的ac时间确定题目的难易
注意对已知关系式的进一步解析
Codeforces:†, ‡, §, ¶分别代表1,2,3,4，一般是对题目信息的补充

原因

不熟悉codeforces
手疏

关键词：是否存在分别代表满足条件