题解 | #S 老师的公式# A题分解质因数解法

//两个数分别跑一下分解质因数 然后统计共同质因子的最小数量
//时间复杂度o（n√n）基本跑满 极限时间卡过


#include<bits/stdc++.h>

#define endl '\n'
#define GG() void(cout<<"-1\n")
#define YES() void(cout << "YES\n")
#define NO() void(cout << "NO\n")
#define debug(x,y); cout<<x<<' '<<y<<endl;
#define  fi first
#define  se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, N = 1e6+10, mod = 998244353;
const LL inf=2e18;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
LL n,m,k;
LL a[N],b[N];
string s1,s2,s3;
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            if(a[i]<=1e5) a[i]+=s;
        }
    if (x > 1&&a[x]<=1e5) a[x]+=1;
}
LL  power(LL  a,LL  b)
{
    if(b<0) return 0;
    LL  res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b >>= 1;
    }
    return res;
}
void find(LL x)
{
    for (LL i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            b[i]+=s;
        }
    if (x > 1) b[x]+=1;
}
void solve() {
    cin>>n;
    LL res=(LL)(n+1)*n/2ll;
    LL ans=1;
    for (int i = 2; i <= n; i++) {
        divide(i);
    }
    find(res);
    LL cc=1;
    for(LL i =2;i<=n;i++)
    {
        if(b[i]>=1&&a[i]>=1)
        {
            LL t=min(b[i],a[i]);
            cc*=power((LL)i,(LL)t);
        }
    }
    cout<<cc<<endl;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int xzx_123=1;
    //cin >> xzx_123;
    while (xzx_123 -- ) solve();
    return 0;
}