题目链接

题意

用一个绳子去包绕一个三维空间的单位立方体，要求绳子有一段和向量 $(a,b,0)$ 平行。求最少需要的绳子长度。$a,b \leq 10^{18}$

题解

绕绳子问题由于会循环多个面，所以我们首先考虑将这个东西展开在无限的二维平面上，这样跳跃到另一个面就可以看作是走到相邻的面了。

考虑一个形象的过程：先从结束的位置把绳子断开，然后我们按照需求往上或者往右滚动，这个绳子也会被留在平面上形成一条直线，最终没有绳子的时候停下来。

那么我们可以看成是这个立方体在沿着直线 $(a,b)$ 滚动，每次可以选择往右或往上，要求底面一直和直线有交点，并且停留在 $k(a,b)$ 位置，要求在停止的时候和一开始的正方体的位置是完全相同的。于是我们可以将正方体的六个面标号，每次往右和往上就是两个置换，不妨记作 $A,B$。我们只需要求出 $(0,0) \to (a,b)$ 的置换是什么，假设是 $C$，我们就是要找最小的 $x$，满足 $C^x = I$，显然 $x \leq 6!$ 所以可以直接暴力（当然大了的时候 BSGS 也不是不可以）。现在问题就是要求出立方体沿着从 $(0,0) \to (a,b)$ 的置换是什么。

设 $f(a,b,A,B)$ 表示我们要求的这个问题，考虑能否往类欧上去凑。假设 $a \geq b$ ，那么我们从 $(0,0)$ 开始，肯定先走 $\lfloor \frac{a}{b} \rfloor$ 个 $A$，再走 $1$ 个 $B$。我们把这个东西看成第二维的方向，这样的方向有 $b$ 个；除了这些我们还需要走 $a \bmod b$ 个 $A$，但是我们并不清楚它在哪里，不过我们可以递归，也就是递归成 $f(a \bmod b,b,A,A^{\lfloor \frac{a}{b} \rfloor}B)$；对于 $a < b$ 也可以类似的取模。在 $a=0$ 或 $b=0$ 的时候特判输出即可。复杂度 $O(\log a + 6! \times 6)$。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

using perm = std::array<int,6>;

perm operator * (perm A,perm B){
    perm res;
    FOR(i,0,5) res[i] = B[A[i]];
    return res;
}

inline perm qpow(perm a,LL n){
    perm res;FOR(i,0,5) res[i] = i;
    while(n){
        if(n&1) res = res*a;
        a = a*a;
        n >>= 1;
    }
    return res;
}

perm work(LL a,LL b,perm A,perm B){
    if(!a) return qpow(B,b);
    if(!b) return qpow(A,a);
    if(a >= b) return work(a%b,b,A,qpow(A,a/b)*B);
    else return work(a,b%a,A*qpow(B,b/a),B);
}

int main(){
    perm A = {0,2,3,5,4,1},B = {5,1,0,3,2,4};
    LL a,b;scanf("%lld%lld",&a,&b);
    if(!a || !b){
        puts("4");
        return 0;
    }
    LL g = std::__gcd(a,b);a /= g;b /= g;
    perm tmp = work(a,b,A,B);
    int k = 0;perm res;FOR(i,0,5) res[i] = i;
    while(true){
        res = res*tmp;++k;
        bool flag = 1;FOR(i,0,5) flag &= (res[i]==i);
        if(flag) break;
    }
    printf("%.15lf\n",k*std::sqrt(1.0*a*a+1.0*b*b));
    return 0;
}