A. Greatest Convex

You are given an integer (k). Find the largest integer (x), where (1≤x<k), such that (x!+(x−1)!)† is a multiple of ‡ (k), or determine that no such (x) exists.

† (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).

Input
The 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)).

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

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

Example
input

4
3
6
8
10

output

2
5
7
9

Note
In 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)且(x!+(x−1)!) % (k==0)，输出(x)的最大值，否则输出(-1)

思路

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

代码

#include<iostream>
using namespace std;
int k,t;

int main(){
	cin >> t;
	while(t -- ){
		cin >> k;
		cout << k - 1 << endl;
	}
}

解题历程

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

经验总结

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

原因

1. 不熟悉codeforces
2. 手疏