时间限制	内存限制
`1000 ms`	`65536 KB`

# 题目描述

数学之神讨厌素数，「暮念」因为证明了 “任一大于 $2$ 的偶数都可写成两个素数之和” 而惹恼了数学之神，被流放到了一个名为「悲寂瀛」的异世界，他的好朋友「瑄瑄」也因受牵连而被一同流放。该世界被分割成无限个独立的空间，每个空间都以坐标点 $(x,y)$ 来标记，「暮念」被关押在坐标为 $(1,1)$ 的空间「CVBB」，而「瑄瑄」被困在遥远的未知空间「QLV」中，她所在的坐标为 $(r,s)$ 。各空间之间存在着时空乱流，阻止犯人穿越，但好在「暮念」掌握了一系列蕴含时空法则的秘术，可以突破乱流干扰，从一个坐标移动到另一个坐标。秘术介绍如下：

秘术 1：从 $(x,y)$ 移动到 $(x,y−x)$ ；

秘术 2：从 $(x,y)$ 移动到 $(x−y,y)$ ；

秘术 3：从 $(x,y)$ 移动到 $(a \times x,y)$ ；

秘术 4：从 $(x,y)$ 移动到 $(x,a×y)$ 。

其中 $a$ 是被数学之神诅咒过的素数。

现在「暮念」需要施展有限次秘术，从空间「CVBB」移动到空间「QLV」以解救「瑄瑄」，请你帮助他判断能否完成解救任务。

# 输入格式

本题有多组数据。

第一行输入 $1$ 个整数 $n$ ，表示数据组数，保证 $1 \le n \le 2^{10}$ 。

接下来输入 $n$ 行，每行 $3$ 个整数 $a, r, s$ ，保证 $a$ 为素数， $1 \le a \le 2^{31} − 1, 1 \le r,s \le 10^{18}$ 。

# 输出格式

对于每组数据，输出一行：

如果能，输出 iloveyou ；

如果不能，输出 seeyouagain 。

# 输入样例

	3
	2 6 9
	2 4 7
	7 14 21

# 输出样例

	seeyouagain
	iloveyou
	iloveyou

# 样例解释

第一组数据：无法通过秘术从 $(1,1)$ 移动到 $(6,9)$ 。

第二组数据：可以通过秘术按以下路径到达： $(1,1)→(1,2)→(1,4)→(1,8)→(1,7)→(2,7)→(4,7)$ 。

第三组数据：可以通过秘术按以下路径到达： $(1,1)→(7,1)→(6,1)→(5,1)→(4,1)→(3,1)→(2,1)→(2,7)→(2,5)→(2,3)→(14,3)→(14,21)$ 。

# 题解：最大公因数

为什么会想到最大公因数？注意到题目里的 “秘术”，加加减减让人联想到辗转相减 / 除法求最大公因数，而乘法操作相当于将最大公因数翻 $a$ 的次幂倍。

想到这里就可以开始写题了，~~赛场上谁有时间给你严格证明这个结论~~，以下是对这个结论的严格证明：

必要性：对于前两个秘术， $\gcd (x, y)$ 保持不变；对于后两个秘术， $\gcd (x, y)$ 不变或变为原来的 $a$ 倍。所以若一个点能从点 $(1, 1)$ 到达，则必然有 $\gcd (x, y) = a^k$ 。

充分性：若一个点 $(x, y)$ 满足 $\gcd (x, y) = a^k$ ，下归纳证明其必然能从点 $(1, 1)$ 到达。

当 $x + y = 2$ 时， $(x, y)$ 即为 $(1, 1)$ ，显然可以到达。
假设对于所有满足 $x + y \le n - 1$ 且 $\gcd (x, y) = a^k$ 的点均能从点 $(1, 1)$ 到达，证明对于所有满足 $x + y = n$ 且 $\gcd (x, y) = a^k$ 的点也可到达，其中 $n > 2$ 。
- 若 $x$ 和 $y$ 中至少有一个为 $a$ 的倍数，不妨设 $x$ 为 $a$ 的倍数，根据归纳假设，点 $\left( \dfrac x a, y \right)$ 可到达，故点 $(x, y)$ 可到达。
- 若 $x$ 和 $y$ 均不为 $a$ 的倍数且 $x \not = y$ ，不妨设 $x > y$ ，存在 $0 \le m \le a - 1$ ，使得 $a | x + my$ 。构造点 $\left( \dfrac {x + my} a, y \right)$ ，则 $\dfrac {x + my} a + y < x + y = n$ 且 $\gcd \left( \dfrac {x + my} a, y \right) = a^{k'}$ ，根据归纳假设，点 $\left( \dfrac {x + my} a, y \right)$ 可到达，故点 $(x, y)$ 也可以到达。
- 若 $x, y$ 均不为 $a$ 的倍数且 $x = y$ ，则 $\gcd (x, y) = x = y = a^k = a^0 = 1$ ，此时 $n = x + y = 2$ 与 $n > 2$ 的假设矛盾。

综上所述，对于给定点 $(x, y)$ ，只需通过辗转相除法求出 $\gcd (x, y)$ ，再判断 $\gcd (x, y)$ 是否为 $a$ 的 $k$ 次幂即可。

时间复杂度： $O(T \log a)$ ，其中 $T$ 为测试数据组数。

参考代码：

	#include <stdio.h>
	#include <stdbool.h>

	typedef long long ll;

	ll gcd(ll a, ll b)
	{
	return b ? gcd(b, a % b) : a;
	}

	int main()
	{
	// freopen("I.in", "r", stdin);
	// freopen("I.out", "w", stdout);

	int T;
	scanf("%d", &T);

	while (T -- )
	{
	int a;
	ll r, s;
	scanf("%d%lld%lld", &a, &r, &s);
	ll g = gcd(r, s);
	bool flag = true;

	while (g > 1)
	{
	if (g % a != 0)
	{
	flag = false;
	break;
	}

	g /= a;
	}

	if (flag)
	puts("iloveyou");
	else
	puts("seeyouagain");
	}

	return 0;
	}

数论最大公因数