NC244674. 互质
描述
输入描述
第一行只有一个正整数T，表示询问的数量。 接下来的T行，每行一个正整数n，表示询问的数字。1 <= T <= 10^6，4 <= n <= 10^16
输出描述
本题采用special judge。输出一共T行，每次询问分别输出一个整数，如果存在一个满足上述条件的x，输出这个x，否则输出-1。
示例1
输入:
2 6 9
输出:
-1 4
示例2
输入:
4 4 6 8 11
输出:
1 -1 3 4
C++(g++ 7.5.0) 解法, 执行用时: 597ms, 内存消耗: 26584K, 提交时间: 2022-10-25 02:49:28
#include<bits/stdc++.h>
typedef long long ll;
int main(){
int t;
scanf("%d",&t);
while(t--){
ll n;
scanf("%lld",&n);
ll x=(n+3)/4;
ll y=n/2;
ll flag=-1;
for(ll i=x;i<=y;i++){
if(std::__gcd(i,n)==1){
flag=i;
break;
}
}
printf("%lld\n",flag);
}
}
C++(clang++ 11.0.1) 解法, 执行用时: 426ms, 内存消耗: 16068K, 提交时间: 2022-12-06 10:21:31
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
int t;
cin>>t;
while(t--)
{
ll n;
scanf("%lld",&n);
if(n==6)
cout<<-1<<endl;
else{
printf("%lld\n",(n-1)/2);
}
}
}