问题 1053. -- 欧几里得

1053: 欧几里得

时间限制: 1 Sec  内存限制: 64 MB
提交: 1  解决: 1
[上一题][提交][讨论版][状态][下一题]

题目描述

已知gcd(a,b)表示a,b的最大公约数。

现在给你一个整数n，你的任务是在区间[1,n)里面找到一个最大的x，使得gcd(x,n)等于1。

输入 [ojld.in]

输入文件的第一行是一个正整数T，表示有T组测试数据
接下来有T行，每行有一个正整数n (1<=n<=100000)。

输出 [ojld.out]

每组测试输出要求x。

样例输入

2
4
7

样例输出

3
6

提示

标签

小菜鸟

[上一题][提交][讨论版][状态][下一题]