Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <set>
- #include <vector>
- #include <map>
- #include <string>
- #include <algorithm>
- #include <utility>
- #include <cstring>
- #include <iomanip>
- #include <queue>
- #include <stack>
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- using namespace std;
- #define forr(i, a, b) for(int i = a; i < int(b); ++i)
- #define forn(i, n) forr(i, 0, n)
- #define pb push_back
- #define mp make_pair
- #define fst first
- #define snd second
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pii;
- ll gcd(ll a, ll b){return a?gcd(b%a,a):b;}
- ll mulmod(ll a, ll b, ll m) {
- ll r=a*b-(ll)((long double)a*b/m+.5)*m;
- return r<0?r+m:r;
- }
- ll expmod(ll b, ll e, ll m){
- if(!e)return 1;
- ll q=expmod(b,e/2,m);q=mulmod(q,q,m);
- return e&1?mulmod(b,q,m):q;
- }
- bool is_prime_prob(ll n, int a){
- if(n==a)return true;
- ll s=0,d=n-1;
- while(d%2==0)s++,d/=2;
- ll x=expmod(a,d,n);
- if((x==1)||(x+1==n))return true;
- forr(_,0,s-1){
- x=mulmod(x,x,n);
- if(x==1)return false;
- if(x+1==n)return true;
- }
- return false;
- }
- bool rabin(ll n){ // true iff n is prime
- if(n==1)return false;
- int ar[]={2,3,5,7,11,13,17,19,23};
- forr(i,0,9)if(!is_prime_prob(n,ar[i]))return false;
- return true;
- }
- ll rho(ll n){
- if(!(n&1))return 2;
- ll x=2,y=2,d=1;
- ll c=rand()%n+1;
- while(d==1){
- x=(mulmod(x,x,n)+c)%n;
- y=(mulmod(y,y,n)+c)%n;
- y=(mulmod(y,y,n)+c)%n;
- if(x>=y)d=gcd(x-y,n);
- else d=gcd(y-x,n);
- }
- return d==n?rho(n):d;
- }
- void fact(ll n, map<ll,int>& f){ //O (lg n)^3
- if(n==1)return;
- if(rabin(n)){f[n]++;return;}
- ll q=rho(n);fact(q,f);fact(n/q,f);
- }
- struct num{
- map<ll,int> M;
- num() = default;
- num(map<ll,int> M): M(M) {}
- num operator * (const num &B) const {
- map<ll,int> ans;
- ll k, v;
- for(auto &x : M){
- tie(k, v) = x;
- ans[k] += v;
- }
- for(auto &x : B.M){
- tie(k, v) = x;
- ans[k] += v;
- }
- return ans;
- }
- bool canBeDividedBy(const num &X) const {
- ll k, v;
- for(auto &x : M){
- tie(k,v) = x;
- if(!X.M.count(k)) return false;
- if(v < X.M.find(k)->snd) return false;
- }
- return true;
- }
- num operator / (const num &B) const {
- map<ll,int> ans;
- ll k, v;
- for(auto &x : M){
- tie(k,v) = x;
- ans[k] += v;
- }
- for(auto &x : B.M){
- tie(k,v) = x;
- ans[k] -= v;
- if(ans[k] == 0) ans.erase(k);
- }
- return ans;
- }
- };
- const int MAXN = 1024;
- int N;
- vector<num> V(MAXN);
- pair<vector<int>, bool> solve(num n){
- if(n.M.size() == 0) return {vector<int>(), 1};
- vector<int> best;
- bool found = false;
- // probar desde el primo mas grande de n
- for(ll d = prev(n.M.end())->first; d < N; d++){
- if(n.canBeDividedBy(V[d])){
- auto res = n / V[d];
- auto sres = solve(res);
- if(sres.snd == 0) continue;
- if(!found or best.size() > sres.fst.size()){
- found = true;
- best = sres.fst;
- best.pb(d);
- }
- }
- }
- return found ? make_pair(best, 1) : make_pair(vector<int>(), 0);
- }
- int main(){
- //freopen("input.txt", "r", stdin);
- ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
- cin >> N;
- forr(i,2,N+1){
- map<ll,int> m;
- fact(i,m);
- V[i] = num(m) * V[i-1];
- }
- auto ans = solve(V[N]);
- if(ans.snd == 0){
- cout << "No solution\n";
- return 0;
- }
- // print ans
- cout << N << "! = ";
- forn(i,ans.fst.size()){
- if(i) cout << " * ";
- cout << ans.fst[i] << "!";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement