Responsive image

问题 1493 --欧几里得

1493: 欧几里得

时间限制: 1 Sec  内存限制: 128 MB
提交: 9  解决: 5
[提交][状态][讨论版][命题人:]

题目描述

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

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

输入描述

输入文件的第一行是一个正整数T，表示有T组测试数据

接下来有T行，每行有一个正整数n (1<=n<=10^1000)。

输出描述

每组测试输出要求x。

样例输入

2
4
7

样例输出

3
6

来源

zj 

[提交][状态]
ACM算法攻关部