fork download
copy 
  1. #include <iostream>
  2. #include <math.h>
  3. #define size 10000
  4. #define mod 1000000007
  5. using namespace std;
  6.  
  7. int power(int a,int b){
  8. 	int res=1;
  9. 	while(b>0){
  10. 	if(b&1)
  11. 	res=(res*a)%mod;
  12. 	b=b>>2;
  13. 	a=(a*a)%mod;
  14. 	}
  15. 	return res;
  16. }
  17.  
  18. int main() {
  19. 	// your code goes here
  20. 	//generate smallest prime factor from 1 - m ;
  21. 			int spf[1+size]={0};
  22. 			spf[0]=spf[1]=1;
  23. 			for(int i=2;i<=size;i++)
  24. 			spf[i]=i;
  25. 			for(int i=4;i<=size;i=i+2)
  26. 			spf[i]=2;
  27. 			for(int i=3;i*i<size;i++){
  28. 			if(spf[i]==i)
  29. 			{
  30. 				for(int j=i*i;j<size;j+=i){
  31. 					if(spf[j]==j){
  32. 						spf[j]=i;
  33. 					}
  34. 				}
  35. 			}
  36. 			}
  37. 	int t;
  38. 	cin>>t;
  39. 	while(t--){
  40. 		int n,m;
  41. 		cin>>n>>m;
  42. 		int a[n];
  43. 		for(int i=0;i<n;i++)
  44. 		cin>>a[i];
  45. 		int fact[m+1]={0};
  46. 		for(int i=0;i<n;i++){
  47. 			int num=a[i];
  48. 			//factorise this number
  49. 			int temp[m+1]={0};
  50. 			while(num!=1){
  51. 				if((temp[spf[num]]+1)>fact[spf[num]]){
  52. 				fact[spf[num]]=temp[spf[num]]+1;}
  53. 				temp[spf[num]]++;
  54. 				num=num/spf[num];
  55. 			}
  56. 		}
  57. 		int index=1,ans=1;
  58. 		for(int i=2;i<=m;i++){
  59. 			//prime factorise X=i
  60. 			int c=0,lcm_x=1;
  61. 			int x=i;
  62. 			while(x>1){
  63. 				 c=0;
  64. 				 int p=spf[x];
  65. 				while(x%p==0){
  66. 					c++;
  67. 					x=x/spf[x];
  68. 				}
  69. 				if((c-fact[p])>0)
  70. 				lcm_x*=pow(p,c-fact[p]);
  71. 			}
  72. 							//cout<<"with "<<i<<" --> "<<lcm_x<<endl;
  73.  
  74. 			if(lcm_x>ans)
  75. 			{
  76. 				index=i;
  77. 				ans=lcm_x;
  78. 			}
  79. 		}
  80. 		cout<<index<<"\n";
  81. 		// for(int i=0;i<=m;i++)
  82. 		// {
  83. 		// 	//if(fact[i]!=0)
  84. 		// 	cout<<i<<" -->  "<<fact[i]<<endl;
  85. 		// }
  86. 		// cout<<"terminating"<<endl;
  87. 	}
  88. 	return 0;
  89. }
Success #stdin #stdout 0s 4260KB
comments (?)
stdin
copy 
1
4 10000
9985 9998 9996 9885
stdout
copy 
9997
https://ideone.com/LSJU9H
language:
C++14 (gcc 8.3)
created:
4 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!