UVa 766 Sum of powers (伯努利数)

题意： 求 ，要求M尽量小。

析：这其实就是一个伯努利数，伯努利数公式如下：

伯努利数满足条件B0 = 1，并且

也有

几乎就是本题，然后只要把 n 换成 n-1，然后后面就一样了，然后最后再加上一个即可。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <cmath>

#include <stack>

#include <sstream>

#define debug() puts("++++");

#define gcd(a, b) __gcd(a, b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define freopenr freopen("in.txt", "r", stdin)

#define freopenw freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1e17;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int maxn = 20 + 10;

const int mod = 1e9 + 7;

const int dr[] = {-1, 0, 1, 0};

const int dc[] = {0, 1, 0, -1};

const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

int n, m;

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline bool is_in(int r, int c){

  return r >= 0 && r < n && c >= 0 && c < m;

}

LL lcm(LL a, LL b){

  return a * (b / gcd(a, b));

}

struct Fraction{

  LL mole;

  LL deno;

  Fraction() : mole(0), deno(1){ }

  Fraction(LL m, LL d) : mole(m), deno(d) {  sinal(); }

  void sinal(){

    if(mole < 0 && deno < 0)  mole = -mole, deno = -deno;

    else if(mole >= 0 && deno < 0)  mole = -mole, deno = -deno;

    if(deno == 0)  mole = 1;

  }

  friend Fraction operator + (const Fraction &lhs, const Fraction &rhs){

    LL l = lcm(lhs.deno, rhs.deno);

    LL m = lhs.mole * (l/lhs.deno) + rhs.mole * (l/rhs.deno);

    return Fraction(m, l);

  }

  friend Fraction operator - (const Fraction &lhs, const Fraction &rhs){

    LL l = lcm(lhs.deno, rhs.deno);

    LL m = lhs.mole * (l/lhs.deno) - rhs.mole * (l/rhs.deno);

    return Fraction(m, l);

  }

  friend Fraction operator * (const Fraction &lhs, const Fraction &rhs){

    LL m = lhs.mole * rhs.mole;

    LL d = lhs.deno * rhs.deno;

    LL g = gcd(m, d);

    return Fraction(m / g, d / g);

  }

  friend Fraction operator / (const Fraction &lhs, const Fraction &rhs){

    LL m = lhs.mole * rhs.deno;

    LL d = lhs.deno * rhs.mole;

    LL g = gcd(m, d);

    return Fraction(m / g, d / g);

  }

  void print(){

    printf("%lld / %lld\n", mole, deno);

  }

};

Fraction C[maxn][maxn];

Fraction B[maxn];

void init(){

  for(int i = 0; i < 25; ++i)

    C[i][0] = C[i][i] = Fraction(1, 1);

  for(int i = 2; i < 25; ++i)

    for(int j = 1; j < i; ++j)

      C[i][j] = C[i-1][j] + C[i-1][j-1];

  B[0] = Fraction(1, 1);

  for(int i = 1; i < 23; ++i){

    for(int j = 0; j < i; ++j)

      B[i] = B[i] + C[i+1][j] * B[j];

    B[i] = B[i] * Fraction(-1LL, i+1LL);

  }

}

Fraction ans[maxn];

int main(){

  init();

  int T;  cin >> T;

  while(T--){

    scanf("%d", &n);

    LL l = 1;

    for(int i = 1; i <= n+1; ++i){

      ans[i] = C[n+1][i] * B[n+1-i] * Fraction(1LL, n+1LL);

      l = lcm(l, ans[i].deno);

    }

    ans[n] = ans[n] + Fraction(1LL, 1LL);

    printf("%lld", l);

    for(int i = n+1; i > 0; --i)

      printf(" %lld", l / ans[i].deno * ans[i].mole);

    printf(" 0\n");

    if(T)  printf("\n");

  }

  return 0;

}