Description
You are hired by french NSA to break the RSA code used on the Pink Card. The easiest way to do that is to factor the public modulus and you have found the fastest algorithm to do that, except that you have to solve a subproblem that can be modeled in the following way. Let calP =p1,p2,…,pn be a set of prime numbers. If S=s1,s2,…,su and T=t1,…,tv are formed with elements of calP , then S*T will denote the quantity displaystyles1∗s2∗cdotcdotcdot∗su∗t1∗t2∗cdotcdotcdot∗tv.
We call relation a set of two primes p,q, where p and q are distinct elements of calP . You dispose of a collection of R relations Si=pi,qi and you are interested in finding sequences of these, Si1,Si2,...,Sik such that displaystyleSi1∗Si2∗cdotcdotcdot∗Sik
is a perfect square.
The way you look for these squares is the following. The ultimate goal is to count squares that appear in the process. Relations arrive one at a time. You maintain a collection calC of relations that do not contain any square subproduct. This is easy: at first, calC is empty. Then a relation arrives and calC begins to grow. Suppose a new relation p,q arrives. If no square appears when adding p,q to calC , then p,q is added to the collection. Otherwise, a square is about to appear, we increase the number of squares, but we do not store this relation, hence calC keeps the desired property. Let us consider an example. First arrives S1=2,3 and we put it in calC ; then arrives S2=5,11,S3=3,7 and they are stored in calC . Now enters the relation S4=2,7 . This relation could be used to form the square: $displaystyle S_1*S_3*S_4 = (2*3)(3*7)(2*7) = (2*3*7)^2.$
So we count 1 and do not store S4 in calC . Now we consider S5=5,11 that could make a square with S2 , so we count 1 square more. Then S6=2,13 is put into calC . Now S7=7,13 could make the square S1∗S3∗S6∗S7 . Eventually, we get 3 squares.
考虑到把一个数对看成一条边，如果形成了一个完全平方数，那么就形成了一个环。并查集维护即可。
#include<cstdio> #include<cstring> int fa[100010]; int find(int x) { if (fa[x]==x) return x; fa[x]=find(fa[x]); return fa[x]; } int main() { int i,j,k,m,n,p,q,x,y,z,ans,T; scanf("%d",&T); while (T--) { ans=0; scanf("%d%d",&n,&m); for (i=1;i<=n;i++) fa[i]=i; for (i=1;i<=m;i++) { scanf("%d%d",&x,&y); if (find(x)==find(y)) ans++; else fa[fa[x]]=fa[y]; } printf("%d\n",ans); } }