题外话

　　浏览器坏掉了…昨天一下午没发题解，现在只好一块发出去。

简述

　　来做一下传说中的送分题。。。我可能比较智障所以调了好长时间，想是很好想 　　首先考虑 double 暴力，这个没啥好说的，暴力 dfs ，竟然有人用 double 水过去了！ 　　把 1 到100的素数乘起来发现已经爆了 long long ，所以不可能求出 lcm 然后乱搞，那怎么办？？ 　　看下数据规模，发现 T×M 竟然才 105 ？也就是说我们还有再加两个 0 的余地，嗯…立马就想到每个数用素数的幂表示。 　　然后就AC了。

代码

//分解质因数+dfs #include <cstdio> #include <algorithm> #define maxn 100000 #define abs(x) (x>0?x:-x) using namespace std; int N, M, T, head[maxn], nex[maxn], to[maxn], w1[maxn], w2[maxn], tot, prime[100], vis[maxn]; struct num { int q[100], fu; void clear(){for(int i=1;i<=*prime;i++)q[i]=0;} }w[maxn], nb[123], big; int gcd(int a, int b){return !b?a:gcd(b,a%b);} num operator*(num a, int b) { int i; num c; c.clear(); for(i=1;i<=*prime;i++)c.q[i]=a.q[i]+nb[abs(b)].q[i]; c.fu=a.fu^(b<0); return c; } num operator/(num a, int b) { int i; num c; c.clear(); for(i=1;i<=*prime;i++)c.q[i]=a.q[i]-nb[abs(b)].q[i]; c.fu=a.fu^(b<0); return c; } bool cmp(num a, num b) { int i; if(a.fu!=b.fu)return false; for(i=1;i<=*prime;i++)if(a.q[i]!=b.q[i])return false; return true; } void adde(int a, int b, int v1, int v2) { to[++tot]=b;nex[tot]=head[a];head[a]=tot; w1[tot]=v1, w2[tot]=v2; } void init() { int i, j, t; for(i=2;i<=100;i++) { for(j=2;j*j<=i;j++)if(i%j==0)break; if(j*j>i)prime[++*prime]=i; } for(i=2;i<=100;i++) for(j=1;j<=*prime;j++) for(t=i;t%prime[j]==0;nb[i].q[j]++,t/=prime[j]); for(i=1;i<=100;i++)big.q[i]=100; } void build() { int i, j, u, v, x, y; scanf("%d%d",&N,&M); for(i=1;i<=tot;i++)nex[i]=0; for(i=1;i<=N;i++)head[i]=0; tot=0; for(i=1;i<=M;i++)scanf("%d%d%d%d",&u,&v,&x,&y), adde(u,v,x,y), adde(v,u,y,x); for(i=1;i<=N;i++)vis[i]=0; } bool dfs(int pos) { int p; num t; vis[pos]=1; for(p=head[pos];p;p=nex[p]) { t=w[pos]/w1[p]*w2[p]; if(vis[to[p]]) { if(!cmp(w[to[p]],t))return false; } else { w[to[p]]=t; if(!dfs(to[p]))return false; } } return true; } int main() { int T, i, j; bool f; init(); scanf("%d",&T); for(i=1;i<=T;i++) { build(); w[1]=big; f=dfs(1); for(j=1;j<=N;j++)if(!vis[j])f=f and dfs(j); printf("Case #%d: ",i); printf(f?"Yes\n":"No\n"); } return 0; }