【2023NOI模拟赛21】打包 做题记录

有一个边长为 $1$ 的立方体，你要用绳子绑紧这个立方体。绳子需要被绑成一个圈，并且不能经过立方体的顶点。绳子在绑的时候还需要被拉直，即立方体在平面上无限展开后绳子在上面的印记是若干直线。

现在把立方体放到三维空间中，使得各棱与坐标轴平行。给定 $a,b$，你需要找到一种绑法，使得绳子的某部分平行于向量 $(a,b,0)$，并且绳子最短。记 $l$ 为绳子长度，请输出 $l^2\operatorname{mod} 10^9+7$，容易证明这是整数。$T$ 组数据。

$1\le T\le 10^5$，$0\le a,b\le 10^{18}$。

和之前的一道题『环』类似。

不妨先让 $\gcd(a,b)=1$。

考虑让正方体在平面上从 $(0,0)$ 开始，沿着直线 $(a,b)$ 滚动，即向上、向右滚且满足每一步底面都覆盖直线。由于 $\gcd(a,b)=1$ 所以滚动一定是以滚过一个 $a\times b$ 的长方形为周期，那么只需要求最少滚 $r$ 个周期满足滚完之后正方体每个面都是原来的面，$l$ 即为 $r\times\sqrt{a^2+b^2}$。

考虑把正方体的每个面标号，那么滚动就可以看成置换，则只需要求出沿对角线滚过 $a\times b$ 的长方形对应的置换 $p$ 即可。

考虑设向上滚的置换为 $x$，向右滚的置换为 $y$，先来考虑 $8\times 3$ 的长方形，显然有 $p=xxxyxxxyxxy=x(xxy)x(xxy)(xxy)$，不妨把 $xxy$ 看作 $y'$，那么我们就成功把问题规模从 $8\times 3$ 缩小到了 $2\times 3$。

发现这样做相当于把向右一格对应成向上两格再向右一格，类似辗转相除：

那么滚过 $a\times b$ 的长方形对应的置换 $p$ 可以这样求：

• $a=0$ 则 $p=y$，$b=0$ 则 $p=x$；
• $a\ge b$ 则令 $a=a\operatorname{mod} b$，$y=x^{\lfloor\frac{a}{b}\rfloor}y$，递归；
• $b>a$，则令 $b=b\operatorname{mod} a$，$x=y^{\lfloor\frac{a}{b}\rfloor}x$，递归；

求出 $p$ 之后暴力枚举计算 $r$ 即可。

代码如下：

// Problem: #207. 打包
// Contest: Hydro
// URL: http://oiclass.com/d/AKNOI/p/207
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int p=1000000007;

struct node
{
	int a[7];
	inline node(){memset(a,0,sizeof(a));}
	inline node(int x,int b,int c,int d,int e,int f){a[1]=x,a[2]=b,a[3]=c,a[4]=d,a[5]=e,a[6]=f;}
	inline int &operator[](int x){return a[x];}
	inline node operator*(node b)
	{
		node re;
		for(int i=1;i<=6;i++) re[i]=b[a[i]];
		return re;
	}
	inline void operator=(node b){for(int i=1;i<=6;i++) a[i]=b[i];}
	inline node operator^(long long y)
	{
		node res(1,2,3,4,5,6),x=*this;
		for(;y>0;y>>=1,x=x*x) res=y&1?res*x:res;
		return res;
	}
	inline bool operator!=(node b)
	{
		for(int i=1;i<=6;i++) if(a[i]!=b[i]) return true;
		return false;
	}
	inline void print(){for(int i=1;i<=6;i++) printf("%d ",a[i]);}
};

node x,y,res;

inline long long gcd(long long x,long long y)
{
	if(x==0||y==0) return x+y;
	long long t=x%y;
	while(t!=0) x=y,y=t,t=x%y;
	return y;
}

void exgcd(long long a,long long b)
{
	if(a==0) return res=y,void();
	if(b==0) return res=x,void();
	if(a>b)
	{
		y=(x^(a/b))*y;
		exgcd(a%b,b);
	}
	else
	{
		x=(y^(b/a))*x;
		exgcd(a,b%a);
	}
}

inline void slove()
{
	long long a,b;
	scanf("%lld%lld",&a,&b);
	long long g=gcd(a,b);
	a/=g,b/=g;
	x=node(6,2,5,4,1,3),y=node(2,3,4,1,5,6);
	exgcd(a,b);
	// res.print(),printf("\n");
	int ans=1;
	node pre=res;
	while(pre!=node(1,2,3,4,5,6))
	{
		pre=pre*res;
		ans++;
	}
	// printf("%d\n",ans);
	// res.print(),printf("\n");
	node tmp=res*res;
	// tmp.print(),printf("\n");
	a%=p,b%=p;
	printf("%lld\n",(a*a%p+b*b%p)%p*ans%p*ans%p);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}