Advertisement
Guest User

Untitled

a guest
Jul 21st, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.95 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement