题目分析:公式还是蛮好推的,每增加一个‘M’就增加4条边,每条边和之前i个‘M’相交得到4*i个空间,再加上两个‘M’之间又形成一个空间,则增加第i+1个‘M’边增加了i*4+1个空间,最后可得公式f(n)=8*n*n-7*n+1。
这样算不算完了呢?显然不是,因为n高达1e12,long long也存不下,解决方法很多,如果用java则需要用读入优化,否则超时,我则用了高精度解决。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define For( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define rev( i , a , b ) for ( int i = a ; i >= b ; -- i ) const int M = 10000 ; struct BigInt { int digit[10] ; int length ; BigInt () { length = 0 ; memset ( digit , 0 , sizeof digit ) ; } BigInt ( LL number ) { length = 0 ; memset ( digit , 0 , sizeof digit ) ; while ( number ) { digit[length ++] = number % M ; number /= M ; } } int operator [] ( const int index ) const { return digit[index] ; } int& operator [] ( const int index ) { return digit[index] ; } BigInt fix () { while ( length && digit[length - 1] == 0 ) -- length ; return *this ; } BigInt operator + ( const BigInt& a ) const { BigInt c ; c.length = max ( length , a.length ) + 1 ; int add = 0 ; rep ( i , 0 , c.length ) { add += a[i] + digit[i] ; c[i] = add % M ; add /= M ; } return c.fix () ; } BigInt operator - ( const BigInt& a ) const { BigInt c ; c.length = max ( a.length , length ) ; int del = 0 ; rep ( i , 0 , c.length ) { del += digit[i] - a[i] ; c[i] = del ; del = 0 ; if ( c[i] < 0 ) { int tmp = ( c[i] - 1 ) / M + 1 ; c[i] += tmp * M ; del -= tmp ; } } return c.fix () ; } BigInt operator * ( const BigInt& a ) const { BigInt c ; c.length = a.length + length ; rep ( i , 0 , length ) { int mul = 0 ; For ( j , 0 , a.length ) { mul += digit[i] * a[j] + c[i + j] ; c[i + j] = mul % M ; mul /= M ; } } return c.fix () ; } void show () { printf ( "%d" , digit[length - 1] ) ; rev ( i , length - 2 , 0 ) printf ( "%04d" , digit[i] ) ; printf ( "\n" ) ; } } ; LL n ; void scanf ( LL& x , char c = 0 ) { while ( ( c = getchar () ) < '0' || c > '9' ) ; x = c - '0' ; while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ; } void solve () { scanf ( n ) ; if ( n <= 1000000000 ) printf ( "%I64d\n" , 8 * n * n - 7 * n + 1 ) ; else { BigInt a = n ; a = a * ( a * 8 - 7 ) + 1 ; a.show () ; } } int main () { int T , cas = 0 ; scanf ( "%d" , &T ) ; while ( T -- ) { printf ( "Case #%d: " , ++ cas ) ; solve () ; } return 0 ; }