已知gcd(a,b)表示a,b的最大公约数。
现在给你一个整数n，你的任务是在区间[1,n)里面找到一个最大的x，使得gcd(x,n)等于1。
1493: 欧几里得
时间限制: 1 Sec 内存限制: 128 MB提交: 9 解决: 5
[提交][状态][讨论版][命题人:]
题目描述
输入描述
输入文件的第一行是一个正整数T，表示有T组测试数据
接下来有T行，每行有一个正整数n (1<=n<=10^1000)。
输出描述
每组测试输出要求x。
样例输入
2
4
7
样例输出
3
6
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版