考虑$|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;
}
最后一次更新于2020-05-19
0 条评论