H-你相信爱情吗？

NC200613. H-你相信爱情吗？

描述

牛郎与织女的故事想必大家都耳熟能详吧，织女真的太爱牛郎了，为了和牛郎在一起，不惜下凡与天庭作对，最后他们俩个还是被硬生生的分离开。织女有一天突然想，要是牛郎不爱她了她得怎么办，由此，织女想考验一下牛郎到底爱不爱她。考验如下：一开始，牛郎和织女在同一个星球上的同一个位置n上，这颗星球上的钻石均匀连续分布在这一星球赤道上；赤道上分布了n个位置，编号为连续的1~n，其中每个位置都放置有一个钻石，总共n个钻石。织女给牛郎一些条件考验限制：
1、牛郎每次只能顺时针移动m步（n往1的方向移动就是顺时针）。
2、牛郎与织女相见后把收集到的钻石给织女。
3、织女要拿到n个钻石。
NOTE：牛郎和织女一开始都在n的位置，织女会一直在n位置等牛郎，牛郎每次结束移动时到达新的位置，都会把这个位置的钻石收集起来，而中间经过的位置不能收集。
牛郎是个执着的人，他会一直走到取完n个钻石，如果永远取不完就输出-1。问：牛郎能不能完成考验？

输入描述

第一行一个整数t代表有t个测试样例(1≤t≤100000)
接下来t行，每行俩个整数n和m，如题面所示，1≤n,m<1e18，m≤n;

输出描述

牛郎若能完成考验就输出最小移动次数，不能就输出-1。

示例1

输入:

1
5 2

输出:

说明:

牛郎分别收集钻石的位置的次序为2 -> 4 -> 1 -> 3 -> 5，刚好到达织女的位置给她n=5颗钻石，移动了5次完成了考验

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 47ms, 内存消耗: 508K, 提交时间: 2020-02-23 13:36:12

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		long long n,m;
        cin>>n>>m;
		if(__gcd(n,m)==1)
			cout<<n<<endl;
		else
			puts("-1");
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 612K, 提交时间: 2019-12-29 14:24:07

#include<bits/stdc++.h>
using namespace std;
long long t,n,m;
int main()
{
 cin>>t;
 while(t--&&cin>>n>>m)
  if(__gcd(n,m)==1)
   cout<<n<<'\n';
  else
   cout<<-1<<'\n';
 return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 415ms, 内存消耗: 25684K, 提交时间: 2019-12-29 14:29:55

from math import gcd
t = int(input())
for cas in range(t):
    n, m = map(int, input().split())
    g = gcd(n, m)
    if g == 1:
        print(n)
    else:
        print(-1)

上一题

下一题

详情