fork download
copy 
  1. /************
  2.  
  3.    Author :- Profesor(Abhishek)
  4.    2020-08-24-15.32.01
  5. **********/
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. #define ll long long
  11. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  12. #define endl "\n"
  13. #define fori(i,a,b) for(ll i=a;i<b;i++)
  14. #define forr(i,a,b) for(ll i=a;i>=b;i--)
  15. #define forit(it,x) for (auto it=(x).begin();it!=(x).end(); it++)
  16. #define all(x) (x).begin(),(x).end()
  17. #define allr(x) (x).rbegin(),(x).rend()
  18. #define eb emplace_back
  19. #define pb push_back
  20. #define mp make_pair
  21. #define fi first
  22. #define se second
  23. #define sll set<ll>
  24. #define vll vector<ll>
  25. #define msl map<string,ll>
  26. #define mll map<ll,ll>
  27.  
  28. const ll MAXN = (ll)1e7;
  29.  
  30. ll i, j, k;
  31.  
  32. vll LCM(MAXN+1);
  33. vector<ll> phi(MAXN+1);
  34.  
  35. vll permuted;
  36.  
  37. void phi_1_to_n() {
  38.  
  39.     phi[0] = 0;
  40.     phi[1] = 1;
  41.     for ( i = 2; i <= MAXN; i++)
  42.         phi[i] = i;
  43.  
  44.     for (i = 2; i <= MAXN; i++) {
  45.         if (phi[i] == i) {
  46.             for (j = i; j <= MAXN; j+=i)
  47.                 phi[j] -= phi[j] / i;
  48.         }
  49.     }
  50.  
  51.     for(i=21 ; i< MAXN+1 ; i++)
  52.     {
  53.         string s1, s2;
  54.         int check = 1;
  55.         s1 = to_string(i);
  56.         s2 = to_string(phi[i]);
  57.         sort(s1.begin(), s1.end());
  58.         sort(s2.begin(), s2.end());
  59.         for(j=0;j<s1.length();j++)
  60.         {
  61.             if(s1[j]!=s2[j])
  62.             {
  63.                 check = 0;
  64.                 break;
  65.             }
  66.         }
  67.         if(check == 1)
  68.             permuted.push_back((ll)i);
  69.     }
  70.  
  71. }
  72.  
  73.  
  74.  
  75. int main()
  76. {
  77.     phi_1_to_n();
  78.     ll t;
  79.     cin >> t;
  80.     while(t--)
  81.     {
  82.         ll n, ans, c=0 ;
  83.         double x=INT_MAX;
  84.         cin >> n;
  85.         for(i=0; i<permuted.size(); i++)
  86.         {
  87.             if(permuted[i]<=n)
  88.             {
  89.                 double division = ((double)permuted[i]/(double)phi[permuted[i]]);
  90.                 if(x >= division)
  91.                 {
  92.                     ans = permuted[i];
  93.                     x=division;
  94.                     c=1;
  95.                 }
  96.  
  97.             }
  98.         }
  99.         if(c==1)
  100.         cout << ans << endl;
  101.         else
  102.             cout << "No solution" << endl;
  103.  
  104.     }
  105.  
  106. }
  107.  
  108.  
Success #stdin #stdout 3.78s 159732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CwKbt8
language:
C++ (gcc 8.3)
created:
4 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!