fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define ll long long int
  8.  
  9. #define maxN 1000000000
  10. #define rootN 31629
  11.  
  12. int A[105],X[105],Y[105],N;
  13. int F[rootN],primecount=0;
  14. int factor[100][rootN];
  15. vector<int> prime;
  16.  
  17. void sieve()
  18. {
  19. int i,j;
  20. for(i=2;i<rootN;i++)
  21. if(F[i]==0) {
  22. prime.pb(i);	//i is a prime number
  23. for(j=i+i;j<rootN;j+=i)
  24. F[j]=1;
  25. }
  26.  
  27. }
  28.  
  29. // 8 12 8 = 2 3 8
  30.  
  31. void factorise() {
  32. int i,j;
  33. for(i=1;i<=N;i++)
  34. for(j=0;j<prime.size();j++) 
  35. while(A[i]%prime[j]==0) {
  36. factor[i][j]++;
  37. A[i]/=prime[j];
  38. }
  39.  
  40. }
  41.  
  42. int min(int a,int b) {
  43. if(a<b)
  44. return a;
  45. else
  46. return b;
  47. }
  48.  
  49. int main() {
  50.  
  51. prime.clear();
  52. sieve();
  53.  
  54. int M,i,j;
  55. cin>>N>>M;
  56.  
  57. ll ans=0;
  58.  
  59. for(i=1;i<=N;i++) 
  60. cin>>A[i];
  61.  
  62. factorise();
  63.  
  64. for(i=0;i<M;i++) {
  65. cin>>X[i]>>Y[i];
  66.  
  67. 	for(j=0;j<prime.size();j++) 
  68. 	if(factor[X[i]][j]>0 && factor[Y[i]][j] >0){
  69.  
  70. 	ans+=min( factor[X[i]][j],factor[Y[i]][j]  );
  71.  
  72. 	if( factor[X[i]][j] < factor[Y[i]][j] ) {
  73. 	factor[Y[i]][j]-=factor[X[i]][j];
  74. 	factor[X[i]][j]=0;
  75. 	}
  76. 	else {
  77. 	factor[X[i]][j]-=factor[Y[i]][j];
  78. 	factor[Y[i]][j]=0;
  79. 	}
  80.  
  81. 	}
  82.  
  83. }
  84.  
  85.  
  86.  
  87. for(i=0;i<M;i++) {
  88. if(A[X[i]]>1 && A[Y[i]]>1 ) {
  89. if(A[X[i]]==A[Y[i]]) {
  90. ans+=1;
  91. A[X[i]]=1;
  92. A[Y[i]]=1;
  93. }
  94. }
  95. }
  96.  
  97. cout<<ans<<"\n";
  98.  
  99. return 0;
  100. }
Success #stdin #stdout 0s 15912KB
comments (?)
stdin
copy 
4 3
8 4 32 8
1 2
2 3
1 4
stdout
copy 
3
https://ideone.com/hcXE5g
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!