fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <unistd.h>
  3. #include <sys/resource.h>
  4. using namespace std;
  5.  
  6. #define sd(a) scanf("%d",&a)
  7. #define ss(a) scanf("%s",a)
  8. #define sl(a) scanf("%lld",&a)
  9. #define clr(a) memset(a,0,sizeof(a))
  10. #define debug(a) printf("check%d\n",a)
  11. #define F first
  12. #define S second
  13. #define MP make_pair
  14. #define PB push_back
  15. #define ll long long
  16. #define N 1000010
  17. #define logn 20
  18. vector<int> v[N], v1[N];
  19. vector<int> tree[N],aux[N];
  20.  
  21. int a[N],cnt[N],var[N],val_var[N],var_cnt,result[N];
  22. int lowest_prime[N], isprime[N];
  23. int in[N], out[N], Time, p[N][logn], l[N], mark[N], in_to_id[N], comp[N], decomp[N];
  24. int dummy_var[N];
  25. int scc[N], scc_count;
  26.  
  27. vector<int> self_inverse[N];
  28. vector<int> Out;
  29. vector<int> order;
  30. vector<int> List[N];
  31.  
  32.  
  33. ll gcd(ll a,ll b)
  34. {
  35. 	ll t;
  36. 	while(b!=0)
  37. 	{
  38. 		t=b;
  39. 		b=a%b;
  40. 		a=t;
  41. 	}
  42. 	return a;
  43. }
  44.  
  45. int getphi(int n)
  46. {
  47. 	int result=0;
  48. 	for(int i=1;i<=n;i++)
  49. 		if(gcd(i,n)==1)
  50. 			result++;
  51. 	return result;
  52. }
  53.  
  54. ll pow1(ll a,ll b,ll mod)
  55. {
  56. 	if(b==0)	return 1%mod;
  57. 	ll ret=pow1(a,b/2,mod);
  58. 	ret=(ret*ret)%mod;
  59. 	if(b&1)	ret=(a*ret)%mod;
  60. 	return ret;
  61. }
  62.  
  63. int lca(int x,int y)
  64. {
  65. 	if(l[x]<l[y])
  66. 		swap(x,y);
  67. 	for(int i=logn-1;i>=0;--i)
  68. 		if(l[p[x][i]]>=l[y])
  69. 			x=p[x][i];
  70. 	if(x==y)
  71. 		return x;
  72. 	for(int i=logn-1;i>=0;--i)
  73. 		if(p[x][i]!=p[y][i])
  74. 		{
  75. 			x=p[x][i];
  76. 			y=p[y][i];
  77. 		}
  78. 	return p[x][0];
  79. }
  80.  
  81. void go(int cur, int par)
  82. {
  83. 	in[cur] = ++Time;
  84. 	in_to_id[in[cur]] = cur;
  85. 	p[cur][0] = par;
  86. 	l[cur] = 1+l[par];
  87. 	for(auto x:tree[cur])
  88. 		if(x!=par)
  89. 			go(x,cur);
  90. 	out[cur] = Time;
  91. }
  92.  
  93. int getNode(int var)
  94. {
  95. 	return abs(var)*2-(var>0);
  96. }
  97. int getVar(int node)
  98. {
  99. 	return (node+1)/2;
  100. }
  101.  
  102. void add_edge(int x, int y)
  103. {
  104. 	v[x].PB(y);
  105. 	v1[y].PB(x);
  106. }
  107.  
  108. void insert_clause(int var1, int var2)
  109. {
  110. 	add_edge(getNode(-var1),getNode(var2));
  111. 	add_edge(getNode(-var2),getNode(var1));
  112. }
  113.  
  114. void scc_dfs1(int cur)
  115. {
  116. 	assert(cur>0);
  117. 	mark[cur]=1;
  118. 	for(auto x:v1[cur])
  119. 		if(!mark[x])
  120. 			scc_dfs1(x);
  121. 	order.PB(cur);
  122. }
  123.  
  124. void scc_dfs2(int cur)
  125. {
  126. 	assert(cur>0);
  127. 	mark[cur]=1;
  128. 	scc[cur] = scc_count;
  129. 	if(result[getVar(cur)]==-1)
  130. 		result[getVar(cur)] = (cur&1);
  131. 	for(auto x:v[cur])
  132. 		if(!mark[x])
  133. 			scc_dfs2(x);
  134. }
  135.  
  136. void clear_data(int LIM)
  137. {
  138. 	for(int i=0;i<=LIM;i++)
  139. 	{
  140. 		tree[i].clear();
  141. 		v[i].clear();
  142. 		v1[i].clear();
  143. 		List[i].clear();
  144. 		result[i] = -1;
  145. 		self_inverse[i].clear();
  146. 		cnt[i] = 0;
  147. 		val_var[i] = 0;
  148. 		var[i] = 0;
  149. 		mark[i] = 0;
  150. 	}
  151.  
  152. 	var_cnt=0;
  153.  
  154. 	Time = 0;
  155.  
  156. 	scc_count = 0;
  157.  
  158. 	order.clear();
  159.  
  160. 	Out.clear();
  161.  
  162. 	if(LIM > 100000)
  163. 		cerr<<LIM<<'\n';
  164. }
  165.  
  166. int main()
  167. {
  168.  
  169. 	clear_data(N-1);
  170. 	// freopen(inputfilenames[fno],"r",stdin);
  171. 	// freopen(outputfilenames[fno],"w",stdout);
  172.  
  173. 	clock_t start = clock();
  174. 	int t,i;
  175. 	//******sieve*********
  176. 	clr(isprime);
  177. 	for(i=2;i<N;i++)
  178. 		isprime[i]=1;
  179. 	for(i=2;i<N;i++)
  180. 	{
  181. 		if(!isprime[i])	continue;
  182. 		for(int j=i;j<N;j+=i)
  183. 		{
  184. 			if(!isprime[j])	continue;
  185. 			isprime[j]=0;
  186. 			lowest_prime[j]=i;
  187. 		}
  188. 	}
  189. 	//********************
  190.  
  191. 	sd(t);
  192.  
  193. 	int n_sum = 0;
  194.  
  195. 	for(int tt=1;tt<=t;tt++)
  196. 	{
  197. 		int n;
  198. 		sd(n);
  199. 		n_sum += n;
  200. 		assert(n>=2);
  201. 		assert(n<=200000);
  202.  
  203. 		int PHI_N = getphi(n);
  204.  
  205.  
  206. 		for(i=1;i<=n;i++)
  207. 		{
  208. 			sd(a[i]);
  209. 			assert(a[i]>=1);
  210. 			assert(a[i]<n);
  211. 			cnt[a[i]]++;
  212. 		}
  213.  
  214. 		for(i=1;i<=n;i++)
  215. 		{
  216. 			int inv = pow1(a[i],PHI_N-1,n);
  217. 			if(gcd(a[i],n)!=1 || cnt[inv]==0)	continue;
  218.  
  219. 			if(a[i] == inv)
  220. 				self_inverse[a[i]].PB(i);
  221. 			else
  222. 			{
  223. 				if(val_var[a[i]] == 0)
  224. 				{
  225. 					val_var[a[i]] = ++var_cnt;
  226. 					val_var[inv] = -var_cnt;
  227. 				}
  228. 				var[i] = val_var[a[i]];
  229. 			}
  230. 			int x = a[i];
  231. 			while(x>1)
  232. 			{
  233. 				int p = lowest_prime[x];
  234. 				while(x%p==0)
  235. 					x/=p;
  236. 				List[p].PB(i);
  237. 			}
  238. 		}
  239.  
  240. 		int fail=0;
  241. 		for(i=1;i<n;i++)
  242. 		{
  243. 			if((int)self_inverse[i].size()>2)
  244. 			{
  245. 				fail=1;
  246. 				break;
  247. 			}
  248. 			if((int)self_inverse[i].size() == 2)
  249. 			{
  250. 				var[self_inverse[i][0]] = ++var_cnt;
  251. 				var[self_inverse[i][1]] = -var_cnt;
  252. 			}
  253. 		}
  254.  
  255. 		for(i=0;i<n-1;i++)
  256. 		{
  257. 			int x,y;
  258. 			sd(x);sd(y);
  259.  
  260. 			tree[x].PB(y);
  261. 			tree[y].PB(x);
  262. 		}
  263. 		l[1] = -1;
  264. 		go(1,1);
  265. 		for(i=1;i<=n;i++)
  266. 			assert(in[i]>=1);
  267. 		if(fail)
  268. 		{
  269. 			printf("No\n");
  270. 			clear_data(max(2*var_cnt,2*n));
  271. 			continue;
  272. 		}
  273. 		for(int j=1;j<logn;j++)
  274. 			for(i=1;i<=n;i++)
  275. 				p[i][j] = p[p[i][j-1]][j-1];
  276. 		for(i=2;i<n;i++)
  277. 		{
  278. 			if(List[i].size() < 2)	continue;
  279.  
  280. 			vector<int> temp;
  281. 			for(auto x:List[i])
  282. 			{
  283. 				mark[x] = 1;
  284. 				temp.PB(in[x]);
  285. 			}
  286.  
  287. 			sort(temp.begin(),temp.end());
  288. 			for(int j=0;j+1<(int)List[i].size();j++)
  289. 				temp.PB(in[lca(in_to_id[temp[j]],in_to_id[temp[j+1]])]);
  290.  
  291. 			set<int> sett(temp.begin(),temp.end());
  292. 			stack<int> s;
  293.  
  294. 			for(int j=1;j<=(int)sett.size();++j)
  295. 				aux[j].clear();
  296.  
  297. 			int comp_cnt=0;
  298. 			bool f=0;
  299. 			for(auto t:sett)
  300. 			{
  301. 				int x=in_to_id[t];
  302. 				comp[x]=++comp_cnt;
  303. 				decomp[comp_cnt]=x;
  304. 				while(!s.empty())
  305. 				{
  306. 					int y=s.top();
  307. 					if(in[x]>=in[y] && in[x]<=out[y])
  308. 						break;
  309. 					s.pop();
  310. 				}
  311. 				if(!s.empty())
  312. 					aux[comp[s.top()]].PB(comp[x]);
  313. 				s.push(x);
  314. 			}
  315. 			for(int j=1;j<=comp_cnt;j++)
  316. 				dummy_var[j] = ++var_cnt;
  317. 			for(int j=1;j<=comp_cnt;j++)
  318. 			{
  319. 				for(auto x:aux[j])
  320. 				{
  321. 					insert_clause(dummy_var[j],-dummy_var[x]);
  322. 					if(mark[decomp[j]] && var[decomp[j]]!=0)
  323. 						insert_clause(-var[decomp[j]],-dummy_var[x]);
  324. 				}
  325. 				if(mark[decomp[j]] && var[decomp[j]]!=0)
  326. 					insert_clause(dummy_var[j],-var[decomp[j]]);
  327.  
  328. 			}
  329. 			for(auto x:sett)
  330. 				mark[in_to_id[x]]=0;
  331. 		}
  332. 		for(i=1;i<=2*var_cnt;i++)
  333. 		{
  334. 			if(mark[i])	continue;
  335. 			scc_dfs1(i);
  336. 		}
  337. 		reverse(order.begin(),order.end());
  338. 		clr(mark);
  339. 		for(auto x:order)
  340. 		{
  341. 			if(mark[x])	continue;
  342. 			++scc_count;
  343. 			scc_dfs2(x);
  344. 		}
  345. 		for(i=1;i<=var_cnt;i++)
  346. 			if(scc[getNode(i)] == scc[getNode(-i)])
  347. 				fail=1;
  348. 		for(i=1;i<=n;i++)
  349. 		{
  350. 			if(var[i] > 0 && result[var[i]])
  351. 				Out.PB(i);
  352. 			if(var[i] < 0 && !result[-var[i]])
  353. 				Out.PB(i);
  354. 		}
  355. 		if(fail)
  356. 		{
  357. 			printf("No\n");
  358. 			clear_data(max(2*var_cnt,2*n));
  359. 			continue;
  360. 		}
  361. 		printf("Yes\n");
  362. 		clear_data(max(2*var_cnt,2*n));
  363.  
  364. 	}
  365. 	clock_t end = clock();
  366. 	cerr <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
  367. 	assert(n_sum<=200000);
  368. }
Success #stdin #stdout #stderr 0.1s 171204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
1000009
Time: 0.014131 seconds
https://ideone.com/zMo3R8
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!