考虑$|x_i|$那么小,不如暴力枚举它们的质因数吧!

就是把一个数拆成$\prod p_i^{c_i}$的形式。

这么一个小trick可以使暴力乘得以实现233。

其实再分析一些小性质

只有环对答案有贡献

那么在环上相邻两点,至少有两条路径可以互相到达。

也就是说如果环有问题,那么在环上的任意一对$(x,y)$的运行也有问题。

所以只要求出$(x,y)$的任意一条路径,之后再比较不在这条路径上的这条的边就可以判断是否影响运行了。

其实从这个结论可以发现,

只要我们遍历一棵树,就可以完美解决此问题

对于根,定义它的旋转次数为$1$

那么对于$x$,$y$的旋转次数就是$\frac{w_x*e_{k_1}}{e_{k_2}},\frac{e_{k_1}}{e_{k_2}}$即为题面中的$\frac{x}{y}$,再转化成质因数形式即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=1e3+5,M=1e4+5;const ull G=31;
const int P[30]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
struct edge{int x,y,next,w1,w2;}a[M<<1];int len,last[N];
void ins(int x,int y,int w1,int w2){a[++len]=(edge){x,y,last[x],w1,w2};last[x]=len;}
int cnt[N][27],lg[105][27],op[N];
bool ve[M<<1],vis[N];
void dfs(int x,int lst)
{
    vis[x]=1;
    for(int k=last[x],y;k;k=a[k].next)
        if(lst!=(k^1))
        {
            y=a[k].y;
            if(vis[y]){ve[k]=ve[k^1]=1;continue;}
            for(int i=1;i<=25;i++)
                cnt[y][i]=cnt[x][i]-lg[abs(a[k].w1)][i]+lg[abs(a[k].w2)][i];
            if(a[k].w1<0||a[k].w2<0)op[y]=op[x]*-1;
            else op[y]=op[x];
            dfs(y,k); 
        }
}
int main()
{
    int T;qr(T);
    for(int i=2;i<=100;i++)
    {
        int x=i;
        for(int j=1;j<=25;j++)
            if(x%P[j]==0)
                while(x%P[j]==0)x/=P[j],++lg[i][j];
    }
    for(int Case=1;Case<=T;Case++)
    {
        memset(last,0,sizeof(last));len=1;
        memset(ve,0,sizeof(ve));memset(vis,0,sizeof(vis));
        memset(cnt,0,sizeof(cnt));memset(op,0,sizeof(op));
        int n,m;qr(n),qr(m);
        for(int i=1,x,y,w1,w2;i<=m;i++)qr(x),qr(y),qr(w1),qr(w2),ins(x,y,w1,w2),ins(y,x,w2,w1);
        for(int i=1;i<=n;i++)
            if(!vis[i])
            {
                op[i]=1;
                dfs(i,0);
            }
        bool bk=1;
        for(int i=1;i<=len;i++)
            if(ve[i])
            {
                ve[i]=ve[i^1]=0;
                int x=a[i].x,y=a[i].y,w1=a[i].w1,w2=a[i].w2;
                int flag=1;
                if(w1<0||w2<0)flag*=-1;
                if(op[x]*flag!=op[y]){bk=0;break;}
                for(int j=1;j<=25;j++)
                    if(cnt[x][j]-lg[abs(w1)][j]+lg[abs(w2)][j]!=cnt[y][j])
                    {
                        bk=0;break;
                    }
                if(!bk)break;
            }    
        printf("Case #%d: ",Case);
        if(!bk)puts("No");
        else puts("Yes");
    }
    return 0;
}