fork(7) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 33000
  4. bool p[MAX];
  5. // find prime number upto 33000, we don't need above 33000 because limit of case is 10^7, and 10^7 root is around 32000
  6. void sieve(){
  7. 	memset(p,0,sizeof(p));
  8. 	p[0]=1;
  9. 	p[1]=1;
  10. 	for(int i=2;i<=MAX;i++){
  11. 		if(!p[i]){
  12. 			for(int j=i*i;j<=MAX;j+=i)
  13. 				p[j]=1;
  14. 		}
  15. 	}
  16. }
  17.  
  18. //find the number of exponent of a prime number if factor is of form a^x * b^y * c^z..., where a,b,c is prime
  19. // It calculates (x+1)*(y+1)*(z+1), The formula I stated in codechef to find number of factor of a number
  20. int process(int n){
  21. 	int ex=1;
  22. 	long long ans=1;
  23. 	if(!(n%2)){
  24. 		while(!(n%2)){
  25. 			n/=2;
  26. 			ex++;
  27. 		}
  28. 	}
  29. 	ans=ans*(ex);
  30. 	for(int i=3;i*i<=n;i+=2){
  31. 		if(!p[i] && !(n%i)){
  32. 			ex=1;
  33. 			while(!(n%i)){
  34. 				n/=i;
  35. 				ex++;
  36. 			}
  37. 			ans*=(ex);
  38. 		}
  39. 	}
  40. 	if(n>1) ans*=2;
  41. 	return ans;
  42. }
  43. // This function checks if number is of power 2, if a number is of power 2 it is of form 10,100,1000,100000 in binary
  44. // that it it will have at most 1 bit as 1 rest will be 0, K&1 checks if a bit is 1 or 0
  45. // if bit is 1 it increments cnt;
  46. // if cnt ==1 , number is of form 10,100,1000,10000 etc etc
  47. // k>>=1 is equivalent to k/2, right shifting the number 10000>>1 will become 1000  
  48. bool powerof2(int k){
  49. 	int cnt=0;
  50. 	while(k>0){
  51. 		if(k&1)	cnt++;
  52. 		k>>=1;
  53. 	}
  54. 	return cnt==1?1:0;
  55. }
  56. int main() {
  57. 	// your code goes here
  58. 	sieve();
  59. 	int t;
  60. 	cin>>t;
  61. 	while(t--){
  62. 		int n;
  63. 		cin>>n;
  64. 		int ans=process(n);
  65.  
  66. 		if(powerof2(ans))
  67. 			cout<<ans<<endl;
  68. 		else{
  69. 			bool fl=0;
  70. 			ans=1;
  71. 			for(int i=2;i*i<=n;i++){
  72. 				if(n%i==0){
  73. 					// if i divides n then n/i is also a factor
  74. 					// therefore we count factors of n/i and i, if n/i has factors of power 2 we output it
  75. 					// but in case of i we cannot output as such because if the number is 40, its factors will be (2,20)
  76. 					// (4,10), (5,8), etc etc
  77. 					// so we cannot output i as such so we save values of i, until the loop exits, when loop exits we have max of i stored as ans
  78. 					// which has number of factors of power 2
  79. 					int a1=process(n/i);
  80. 					int a2=process(i);
  81. 					if(powerof2(a1)){
  82. 						cout<<a1<<endl;
  83. 						cout<<n/i<<endl;
  84. 						fl=1;
  85. 						break;
  86. 					}
  87. 					else if(powerof2(a2))
  88. 						ans=max(ans,a2);
  89. 				}
  90. 			}
  91. 			if(!fl)
  92. 				cout<<ans<<endl;
  93. 		}
  94. 	}
  95. 	return 0;
  96. }
Success #stdin #stdout 0s 16096KB
comments (?)
stdin
copy 
3
17
48
60
stdout
copy 
2
8
24
8
30
https://ideone.com/7HB6SB
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!