AcWing 130. 火车进出栈问题
原题链接
中等
作者:
wjie
,
2020-07-25 20:20:57
,
所有人可见
,
阅读 687
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 12e4 + 5;
int prime[N], exponent[N], cnt;
bool st[N];
void initPrime(int n)
{
st[1] = true;
for (int i = 2; i <= n; i++)
{
if (!st[i]) prime[cnt++] = i;
for (int j = 0; j < cnt && prime[j]*i <= n; j++)
{
st[prime[j]*i] = true;
if (i % prime[j] == 0) break;
}
}
}
int func(int x, int p)
{
int res = 0;
while (x)
{
res += x / p;
x /= p;
}
return res;
}
void multiple(vector<int> &a, int b)
{
int r = 0;
for (int i = 0; i < a.size(); i++)
{
a[i] = a[i] * b + r;
r = a[i] / 10000;
a[i] %= 10000;
}
while (r)
{
a.push_back(r % 10000);
r /= 10000;
}
}
int main()
{
int n;
scanf("%d", &n);
initPrime(2*n);
for (int i = 0; i < cnt; i++)
{
int p = prime[i];
exponent[p] = func(2*n, p) - 2*func(n, p);
}
int m = n + 1;
for (int i = 0; i < cnt && m > 1; i++)
{
int p = prime[i], temp = 0;
while (m % p == 0)
{
temp++;
m /= p;
}
exponent[p] -= temp;
}
vector<int> res;
res.push_back(1);
for (int i = 0; i < cnt; i++)
{
int p = prime[i];
for (int j = 0; j < exponent[p]; j++)
{
multiple(res, p);
}
}
printf("%d", res.back());
for (int i = res.size()-2; i >= 0; i--) printf("%04d", res[i]);
return 0;
}