2013
11-10

# Sum of powers

A young schoolboy would like to calculate the sum

for some fixed natural k and different natural n. He observed that calculating ik for all i (1<=i<=n) and summing up results is a too slow way to do it, because the number of required arithmetical operations increases as n increases. Fortunately, there is another method which takes only a constant number of operations regardless of n. It is possible to show that the sum Sk(n) is equal to some polynomial of degree k+1 in the variable n with rational coefficients, i.e.,

We require that integer M be positive and as small as possible. Under this condition the entire set of such numbers (i.e. M, ak+1, ak, … , a1, a0) will be unique for the given k. You have to write a program to find such set of coefficients to help the schoolboy make his calculations quicker.

The input file contains a single integer k (1<=k<=20).

Write integer numbers M, ak+1, ak, … , a1, a0 to the output file in the given order. Numbers should be separated by one space. Remember that you should write the answer with the smallest positive M possible.

2

6 2 3 1 0


//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;
public class Main
{
static class com
{
BigInteger a,b;//a/b...
{
com ret=new com();
BigInteger lcm;
lcm=b.multiply(C.b).divide(b.gcd(C.b));
ret.b=lcm;
lcm=ret.b.gcd(ret.a);
ret.a=ret.a.divide(lcm);
ret.b=ret.b.divide(lcm);
return ret;
}
com sub(com C)
{
com ret=new com();
BigInteger lcm;
lcm=b.multiply(C.b).divide(b.gcd(C.b));
ret.b=lcm;
ret.a=a.multiply(lcm.divide(b)).subtract((C.a.multiply(lcm.divide(C.b))));
lcm=ret.b.gcd(ret.a);
ret.a=ret.a.divide(lcm);
ret.b=ret.b.divide(lcm);
return ret;
}
void show()
{
System.out.println(a+" / "+b);
}
}

static BigInteger s[][]=new BigInteger[105][105],fac[]=new BigInteger[105],dp[][]=new BigInteger[105][105];
static com B[]=new com[105];
static com buf[] = new com[105];
static void mkstri()
{
int i,j;
com tmp = new com();
for (i = 0; i < 105; ++i) B[i] = new com();
for(i=1;i< 105;++i)
{
dp[i][0]=dp[i][i]=BigInteger.ONE;
for(j=1;j< i;++j)
}
for(i=1;i< 105;++i)
s[i][i]=s[i][1]=BigInteger.ONE;
for(i=2;i< 105;++i)
for(j=2;j< i;++j)
fac[0]=BigInteger.ONE;
for(i=1;i< 105;++i)
fac[i]=fac[i-1].multiply(BigInteger.valueOf(i));
B[0].a=B[0].b=BigInteger.ONE;
for(i=1;i< 105;++i)
{
B[i].a=BigInteger.ZERO;
B[i].b=BigInteger.ONE;
for(j=1;j<=i;++j)
{
tmp.a=fac[j].multiply(s[i][j]);
tmp.b=BigInteger.valueOf(j+1);
if((i+j)%2==0)
else
B[i]=B[i].sub(tmp);
}
}
}

public static void main(String args[]) throws Exception {
Scanner cin=new Scanner(System.in);
mkstri();
BigInteger ans,tmp,G;
int k,i;
for(i=0;i< 105;++i)buf[i]=new com();
while(cin.hasNext())
{
k=cin.nextInt();
//k+1...
ans=BigInteger.ONE;
for(i=0;i<=k;++i)
{
buf[i].b=B[i].b.multiply(BigInteger.valueOf(k+1));
buf[i].a=B[i].a.multiply(dp[k+1][i]);
G=buf[i].a.gcd(buf[i].b);
buf[i].a=buf[i].a.divide(G);
buf[i].b=buf[i].b.divide(G);
ans=ans.multiply(buf[i].b).divide(buf[i].b.gcd(ans));
}
System.out.print(ans);
for(i=0;i<=k;++i)
{
G=ans.divide(buf[i].b);
System.out.print(" "+buf[i].a.multiply(G));
}
System.out.println(" 0");
}
}
}

1. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count