SHARE
TWEET

Untitled

a guest Jul 21st, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <set>
  4. #include <vector>
  5. #include <map>
  6. #include <string>
  7. #include <algorithm>
  8. #include <utility>
  9. #include <cstring>
  10. #include <iomanip>
  11. #include <queue>
  12. #include <stack>
  13.  
  14. #pragma GCC optimize("Ofast")
  15. #pragma GCC optimize("unroll-loops")
  16. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  17.  
  18. using namespace std;
  19.  
  20. #define forr(i, a, b) for(int i = a; i < int(b); ++i)
  21. #define forn(i, n) forr(i, 0, n)
  22. #define pb push_back
  23. #define mp make_pair
  24. #define fst first
  25. #define snd second
  26.  
  27. typedef long long ll;
  28. typedef long double ld;
  29. typedef pair<int, int> pii;
  30.  
  31.  
  32. ll gcd(ll a, ll b){return a?gcd(b%a,a):b;}
  33. ll mulmod(ll a, ll b, ll m) {
  34.     ll r=a*b-(ll)((long double)a*b/m+.5)*m;
  35.     return r<0?r+m:r;
  36. }
  37. ll expmod(ll b, ll e, ll m){
  38.     if(!e)return 1;
  39.     ll q=expmod(b,e/2,m);q=mulmod(q,q,m);
  40.     return e&1?mulmod(b,q,m):q;
  41. }
  42. bool is_prime_prob(ll n, int a){
  43.     if(n==a)return true;
  44.     ll s=0,d=n-1;
  45.     while(d%2==0)s++,d/=2;
  46.     ll x=expmod(a,d,n);
  47.     if((x==1)||(x+1==n))return true;
  48.     forr(_,0,s-1){
  49.         x=mulmod(x,x,n);
  50.         if(x==1)return false;
  51.         if(x+1==n)return true;
  52.     }
  53.     return false;
  54. }
  55. bool rabin(ll n){ // true iff n is prime
  56.     if(n==1)return false;
  57.     int ar[]={2,3,5,7,11,13,17,19,23};
  58.     forr(i,0,9)if(!is_prime_prob(n,ar[i]))return false;
  59.     return true;
  60. }
  61. ll rho(ll n){
  62.     if(!(n&1))return 2;
  63.     ll x=2,y=2,d=1;
  64.     ll c=rand()%n+1;
  65.     while(d==1){
  66.         x=(mulmod(x,x,n)+c)%n;
  67.         y=(mulmod(y,y,n)+c)%n;
  68.         y=(mulmod(y,y,n)+c)%n;
  69.         if(x>=y)d=gcd(x-y,n);
  70.         else d=gcd(y-x,n);
  71.     }
  72.     return d==n?rho(n):d;
  73. }
  74. void fact(ll n, map<ll,int>& f){ //O (lg n)^3
  75.     if(n==1)return;
  76.     if(rabin(n)){f[n]++;return;}
  77.     ll q=rho(n);fact(q,f);fact(n/q,f);
  78. }
  79.  
  80. struct num{
  81.     map<ll,int> M;
  82.     num() = default;
  83.     num(map<ll,int> M): M(M) {}
  84.     num operator * (const num &B) const {
  85.         map<ll,int> ans;
  86.         ll k, v;
  87.         for(auto &x : M){
  88.             tie(k, v) = x;
  89.             ans[k] += v;
  90.         }
  91.         for(auto &x : B.M){
  92.             tie(k, v) = x;
  93.             ans[k] += v;
  94.         }
  95.         return ans;
  96.     }
  97.     bool canBeDividedBy(const num &X) const {
  98.         ll k, v;
  99.         for(auto &x : M){
  100.             tie(k,v) = x;
  101.             if(!X.M.count(k)) return false;
  102.             if(v < X.M.find(k)->snd) return false;
  103.         }
  104.         return true;
  105.     }
  106.     num operator / (const num &B) const {
  107.         map<ll,int> ans;
  108.         ll k, v;
  109.         for(auto &x : M){
  110.             tie(k,v) = x;
  111.             ans[k] += v;
  112.         }
  113.         for(auto &x : B.M){
  114.             tie(k,v) = x;
  115.             ans[k] -= v;
  116.             if(ans[k] == 0) ans.erase(k);
  117.         }
  118.         return ans;
  119.     }
  120. };
  121.  
  122. const int MAXN = 1024;
  123. int N;
  124. vector<num> V(MAXN);
  125.  
  126.  
  127. pair<vector<int>, bool> solve(num n){
  128.     if(n.M.size() == 0) return {vector<int>(), 1};
  129.    
  130.     vector<int> best;
  131.     bool found = false;
  132.    
  133.     // probar desde el primo mas grande de n
  134.     for(ll d = prev(n.M.end())->first; d < N; d++){
  135.         if(n.canBeDividedBy(V[d])){
  136.             auto res = n / V[d];
  137.                        
  138.             auto sres = solve(res);
  139.             if(sres.snd == 0) continue;
  140.            
  141.             if(!found or best.size() > sres.fst.size()){
  142.                 found = true;
  143.                 best = sres.fst;
  144.                 best.pb(d);
  145.             }
  146.         }
  147.     }
  148.    
  149.     return found ? make_pair(best, 1) : make_pair(vector<int>(), 0);
  150. }
  151.  
  152. int main(){
  153.     //freopen("input.txt", "r", stdin);
  154.     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  155.  
  156.     cin >> N;
  157.  
  158.     forr(i,2,N+1){
  159.         map<ll,int> m;
  160.         fact(i,m);
  161.         V[i] = num(m) * V[i-1];
  162.     }
  163.    
  164.     auto ans = solve(V[N]);
  165.     if(ans.snd == 0){
  166.         cout << "No solution\n";
  167.         return 0;
  168.     }
  169.    
  170.     // print ans
  171.     cout << N << "! = ";
  172.     forn(i,ans.fst.size()){
  173.         if(i) cout << " * ";
  174.         cout << ans.fst[i] << "!";
  175.     }
  176.    
  177.    
  178.     return 0;
  179. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top