fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define MOD 1000000007
  3. #define quick ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  4. using namespace std;
  5. typedef long long ll;
  6. typedef long double ld;
  7.  
  8. vector<ll> lastPrime(1000001);
  9. // storing the last prime factor (not smallest) cause its easier
  10. void sieve()
  11. {
  12. 	bool isPrime[1000001];
  13. 	memset(isPrime,true,sizeof(isPrime));
  14. 	for(ll i=2;i<1000001;i++)
  15. 	{
  16. 		if(isPrime[i])
  17. 		{
  18. 			lastPrime[i]=i;
  19. 			for(ll j=i+i;j<1000001;j=j+i)
  20. 			{
  21. 				isPrime[j]=false;
  22. 				lastPrime[j]=i;
  23. 			}
  24. 		}
  25. 	}
  26. }
  27.  
  28. ll fun(ll n)
  29. {
  30. 	map<ll,ll> factors;
  31. 	assert(n<=1000000);
  32. 	while(n!=1)
  33. 	{
  34. 		factors[lastPrime[n]]++;
  35. 		n=n/lastPrime[n];
  36. 	}
  37. 	ll ans=1;
  38. 	for(map<ll,ll>::iterator it=factors.begin();it!=factors.end();it++)
  39. 	{
  40. 		if(it->second%2)
  41. 		{
  42. 			ans=ans*it->first;
  43. 		}
  44. 	}
  45. 	return ans;
  46. }
  47. int main()
  48. {
  49. 	sieve();
  50. 	ll t;
  51. 	cin>>t;
  52. 	while(t--)
  53. 	{
  54. 		ll n;
  55. 		cin>>n;
  56. 		cout<<fun(n)<<endl;
  57. 	}
  58. 	return 0;
  59. }
Success #stdin #stdout 0.04s 11284KB
comments (?)
stdin
copy 
3
2
4
12
stdout
copy 
2
1
3
https://ideone.com/SRY4Gg
language:
C++14 (gcc 8.3)
created:
6 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!