Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Philip_PV
- #include <fstream>
- #include <iostream>
- #include <set>
- #include <map>
- #include <string>
- #include <vector>
- #include <list>
- #include <queue>
- #include <deque>
- #include <stack>
- #include <bitset>
- #include <functional>
- #include <numeric>
- #include <utility>
- #include <sstream>
- #include <iomanip>
- #include <cstdio>
- #include <cstdlib>
- #include <algorithm>
- #include <cassert>
- #include <ctime>
- #include <memory.h>
- #include <cmath>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef unsigned int uint;
- typedef pair<double, double> pdd;
- typedef pair<int, int> pii;
- /*
- #define x first
- #define y second
- //*/
- #ifdef _DEBUG
- #define dbg(x) { cerr << #x << " = " << x << endl; }
- #else
- #define dbg(x) ;
- #endif
- #define forn(_i,_n) for (int _i = 0; _i < (int)(_n); ++_i)
- #define mp make_pair
- #define SIZE 200
- #define mod 1000000
- struct bigint {
- int data[SIZE], size;
- bigint() { }
- inline void zero() {
- memset(data, 0, sizeof(data));
- size = 1;
- }
- inline void one() {
- zero();
- data[0] = 1;
- }
- void norm() {
- int rem = 0;
- forn (i, size) {
- data[i] += rem;
- rem = data[i] / mod;
- data[i] %= mod;
- }
- while (rem) {
- data[size] = rem;
- rem = data[size] / mod;
- data[size] %= mod;
- size++;
- }
- }
- int div(int n, bool d) {
- int rem = 0;
- for (int i = size - 1; i >= 0; i--) {
- int v = data[i] + rem * mod;
- rem = v % n;
- if (d) data[i] = v / n;
- }
- while (size > 1 && !data[size - 1]) size--;
- return rem;
- }
- void print() {
- while (size > 1 && !data[size - 1]) size--;
- printf("%d", data[size - 1]);
- for (int i = size - 2; i >= 0; i--)
- printf("%06d", data[i]);
- }
- inline void mul(int n) {
- forn (i, size)
- data[i] *= n;
- norm();
- }
- };
- void prepare(bigint& a, bigint& b, int n) {
- for (int i = 2; i <= n; i++) {
- bool ok = true;
- for (int j = 2; j < i; j++)
- if (i % j == 0) ok = false;
- int t = n, cnt = 0;
- while (t) cnt += (t/=i);
- if (ok)
- while (cnt-- && !a.div(i, false)) {
- a.div(i, true);
- b.div(i, true);
- }
- }
- }
- bigint A[470], B, ansA[470], ansB[470];
- vector<int> Q;
- int main() {
- /*
- cout << 461 << endl;
- forn (i, 462)
- cout << i << endl;
- return 0;
- */
- forn (i, 470) A[i].one();
- B.one();
- ansA[0].one(); ansB[0].one();
- int t; cin >> t;
- Q.reserve(t);
- forn (i, t) cin >> Q[i];
- int _m = 0;
- forn (i, t) _m = max(_m, Q[i]);
- for (int n = 1; n <= _m; n++) {
- B.mul(n);
- forn (i, n)
- A[i].mul(n - i);
- A[n] = B;
- ansB[n] = B;
- ansA[n].zero();
- forn (i, n + 1) {
- forn (j, A[i].size)
- ansA[n].data[j] += A[i].data[j];
- ansA[n].size = max(ansA[n].size, A[i].size);
- }
- ansA[n].norm();
- }
- forn (i, t) {
- int n = Q[i];
- prepare(ansA[n], ansB[n], n);
- ansA[n].print();
- if (ansB[n].size == 1 && ansB[n].data[0] == 1);
- else {
- putchar('/');
- ansB[n].print();
- }
- putchar('\n');
- }
- flush(cout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement