| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19857 |
2016-02-25T06:20:29 Z |
xhae |
창문 (kriii4_C) |
C++14 |
|
1 ms |
1880 KB |
#include <cstdio>
/**
* Big integer class, optimized for decimal integers.
* Stores and manipulates integers represented as byte arrays,
* where each byte is a decimal digit. If you're looking for
* robust, bug-free, efficient code, keep looking. This is a quick
* and dirty hack. Some day I'll write a templatized BigInt, where
* you will be able to select the base in which to store the
* number. When that day comes, most of this code will be thrown
* away.
*
* BUGS:
* operator-(int) does not work.
*
* BigInt doesn't play nice with long long. Either use int
* or string.
*
* INVARIANTS:
* - capacity is never smaller than 16
* - capacity is not the smallest it can be because every
* modifying member function first grows digits as much as
* it might ever need and then does its job.
* FIELD TESTING:
* - Passed numerous problems on Valladolid, including
* 107, 288, 324, 424, 465, 485, 495, 560, 619, 623, etc.
*
* COMPATIBILITY:
* - This class was written for the g++ compiler and uses some
* of the g++ extensions (like "long double" and the ">?="
* operator). If you want to compile this under Micro$oft's
* "compiler", I don't want to talk to you.
*
* LAST MODIFIED: October 5, 2005
*
* This file is part of my library of algorithms found here:
* http://www.palmcommander.com:8081/tools/
* LICENSE:
* http://www.palmcommander.com:8081/tools/LICENSE.html
* Copyright (c) 2002-2004
* Contact author:
* igor at cs.ubc.ca
**/
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <sstream>
#include <math.h>
using namespace std;
#ifndef min
#define min(x,y) ((x) < (y) ? (x) : (y))
#endif
#ifndef max
#define max(x,y) ((x) > (y) ? (x) : (y))
#endif
class BigInt
{
private:
char *digits;
int size; // number of used bytes (digits)
int capacity; // size of digits
int sign; // -1, 0 or +1
public:
/** Creates a BigInt with initial value n and initial capacity cap **/
BigInt( int n, int cap );
/** Creates a BigInt with initial value n **/
BigInt( int n );
/** Creates a BigInt with initial value floor( d ) **/
BigInt( long double d );
/** Creates a BigInt with value 0 **/
BigInt();
/** Creates a BigInt by reading the value from a string **/
BigInt( string s );
/** Creates a BigInt by reading the value from a C string **/
BigInt( const char s[] );
/** Copy constructor **/
BigInt( const BigInt &n );
/** Assignment operators **/
const BigInt &operator=( const BigInt &n );
const BigInt &operator=( int n );
/** Cleans up **/
~BigInt();
/** Removes any leading zeros and adjusts the sign **/
void normalize();
/** Returns the sign of n: -1, 0 or 1 **/
static int sig( int n );
/** Returns the sign of n: -1, 0 or 1 **/
static int sig( long double n );
/** Returns the number of decimal digits **/
inline int length() { return size; }
/** Arithmetic **/
BigInt operator++();
BigInt operator++( int );
BigInt operator--();
BigInt operator--( int );
BigInt operator-();
BigInt operator+ ( int n );
BigInt operator+ ( BigInt n );
BigInt&operator+=( int n );
BigInt&operator+=( BigInt n );
BigInt operator- ( int n );
BigInt operator- ( BigInt n );
BigInt&operator-=( int n );
BigInt&operator-=( BigInt n );
BigInt operator* ( int n );
BigInt operator* ( BigInt n );
void operator*=( int n );
void operator*=( BigInt n );
BigInt operator/ ( int n );
BigInt operator/ ( BigInt n );
void operator/=( int n );
void operator/=( BigInt n );
int operator% ( int n );
BigInt operator% ( BigInt n );
void operator%=( int n );
void operator%=( BigInt n );
int divide( int n ); // Divides storing quotient in *this and returning the remainder
BigInt divide( BigInt n ); // Divides storing quotient in *this and returning the remainder
BigInt operator* ( long double n ); // Multiplies by a double and truncates (always under-estimates!)
void operator*=( long double n ); // Multiplies by a double and truncates (always under-estimates!)
/** Bitwise arithmetic **/
BigInt operator<< ( int n );
void operator<<=( int n );
BigInt operator>> ( int n ); // Works differently for negative numbers
void operator>>=( int n ); // Works differently for negative numbers
/*
BigInt operator& ( int n );
BigInt operator& ( BigInt n );
void operator&= ( int n );
void operator&= ( BigInt n );
BigInt operator| ( int n );
BigInt operator| ( BigInt n );
void operator|= ( int n );
void operator|= ( BigInt n );
BigInt operator^ ( int n );
BigInt operator^ ( BigInt n );
void operator^= ( int n );
void operator^= ( BigInt n );
BigInt operator~();
*/
/** Concatenation ;-) **/
BigInt operator,( int n );
BigInt operator,( BigInt n );
/** Casting **/
bool operator!();
operator bool();
//operator int(); //XXX: Don't do this!!! It takes precedence over operator+(int,BigInt)
operator string();
/** Comparison **/
bool operator<( BigInt n );
bool operator>( BigInt n );
bool operator==( BigInt n );
bool operator<=( BigInt n );
bool operator>=( BigInt n );
bool operator<( int n );
bool operator>( int n );
bool operator==( int n );
bool operator<=( int n );
bool operator>=( int n );
int compare( BigInt n );
/** Returns the lowest value as an integer (watch out for overflow) **/
int toInt();
/** Returns the value as a decimal string **/
string toString();
/** Outputs decimal value to stdout **/
void print();
/** Outputs the decimal value, with commas **/
void printWithCommas( ostream &out );
private:
/** Expansion **/
void grow();
/** I/O Friends **/
friend istream &operator>>( istream &in, BigInt &n );
friend ostream &operator<<( ostream &out, BigInt n );
/** Logarithms **/
friend long double log2( BigInt x, long double epsilon );
inline friend long double log( BigInt x, long double epsilon );
inline friend long double log10( BigInt x, long double epsilon );
inline friend long double lg( BigInt x, long double epsilon );
inline friend long double ln( BigInt x, long double epsilon );
};
BigInt operator+( int m, BigInt &n )
{
return n + m;
}
BigInt operator-( int m, BigInt &n )
{
return -n + m;
}
BigInt operator*( int m, BigInt &n )
{
return n * m;
}
BigInt operator/( int m, BigInt &n )
{
return BigInt( m ) / n;
}
BigInt operator%( int m, BigInt &n )
{
return BigInt( m ) % n;
}
/** Misc **/
inline bool isDigit( int c )
{
return( c >= ( int )'0' && c <= ( int )'9' );
}
/** Input/Output **/
istream &operator>>( istream &in, BigInt &n ) // FIXME: see inside
{
n.size = 0;
n.sign = 1;
int sign = 1;
int c;
while( ( c = in.peek() ) >= 0 &&
( c == ' ' || c == '\t' || c == '\r' || c == '\n' ) )
in.get();
if( c < 0 || ( c != ( int )'-' && !isDigit( c ) ) )
{
in >> c; // XXX: force in.fail()
return in;
}
if( c == ( int )'-' ) { sign = -1; in.get(); }
// FIXME: Extremely inefficient! Use a string.
while( ( c = in.peek() ) >= 0 && isDigit( c ) )
{
in.get();
n *= 10;
n += ( c - ( int )'0' );
}
n.sign = sign; //XXX: assign n.sign directly after fixing the FIXME
n.normalize();
return in;
}
ostream &operator<<( ostream &out, BigInt n ) //FIXME: make more efficient
{
return out << n.toString();
}
BigInt::BigInt( int n, int cap )
{
cap = max( cap, ( int )sizeof( n ) * 8 );
capacity = cap;
sign = sig( n );
n *= sign;
digits = new char[cap];
memset( digits, 0, cap );
for( size = 0; n; size++ )
{
digits[size] = n % 10;
n /= 10;
}
}
BigInt::BigInt( int n )
{
capacity = 1024;
sign = sig( n );
n *= sign;
digits = new char[capacity];
memset( digits, 0, capacity );
size = 0;
while( n )
{
digits[size++] = n % 10;
n /= 10;
}
}
BigInt::BigInt( long double d )
{
}
BigInt::BigInt()
{
capacity = 128;
sign = 0;
digits = new char[capacity];
memset( digits, 0, capacity );
size = 0;
}
BigInt::BigInt( string s )
{
capacity = max( ( int )s.size(), 16 );
sign = 0;
digits = new char[capacity];
memset( digits, 0, capacity );
istringstream in( s );
in >> ( *this );
}
BigInt::BigInt( const char s[] )
{
capacity = max( ( int )strlen( s ), 16 );
sign = 0;
digits = new char[capacity];
memset( digits, 0, capacity );
istringstream in( s );
in >> ( *this );
}
BigInt::BigInt( const BigInt &n )
{
capacity = n.capacity;
sign = n.sign;
size = n.size;
digits = new char[capacity];
memcpy( digits, n.digits, capacity );
}
const BigInt &BigInt::operator=( const BigInt &n )
{
if( &n != this )
{
if( capacity < n.size )
{
capacity = n.capacity;
delete [] digits;
digits = new char[capacity];
}
sign = n.sign;
size = n.size;
memcpy( digits, n.digits, size );
memset( digits + size, 0, capacity - size );
}
return *this;
}
const BigInt &BigInt::operator=( int n )
{
sign = sig( n );
n *= sign;
for( size = 0; n; size++ )
{
digits[size] = n % 10;
n /= 10;
}
return *this;
}
BigInt::~BigInt()
{
delete [] digits;
}
void BigInt::normalize()
{
while( size && !digits[size-1] ) size--;
if( !size ) sign = 0;
}
int BigInt::sig( int n )
{
return( n > 0 ? 1 : ( n == 0 ? 0 : -1 ) );
}
int BigInt::sig( long double n )
{
return( n > 0 ? 1 : ( n == 0 ? 0 : -1 ) );
}
int BigInt::toInt()
{
int result = 0;
for( int i = size - 1; i >= 0; i-- )
{
result *= 10;
result += digits[i];
if( result < 0 ) return sign * 0x7FFFFFFF;
}
return sign * result;
}
string BigInt::toString()
{
string s = ( sign >= 0 ? "" : "-" );
for( int i = size - 1; i >= 0; i-- )
s += ( digits[i] + '0' );
if( size == 0 ) s += '0';
return s;
}
void BigInt::print() //FIXME: make more efficient
{
cout << toString();
}
void BigInt::printWithCommas( ostream &out )
{
if( sign < 0 ) out.put( '-' );
for( int i = size - 1; i >= 0; i-- )
{
out.put( digits[i] + '0' );
if( !( i % 3 ) && i ) out.put( ',' );
}
if( size == 0 ) out.put( '0' );
}
void BigInt::grow()
{
char *olddigits = digits;
int oldCap = capacity;
capacity *= 2;
digits = new char[capacity];
memcpy( digits, olddigits, oldCap );
memset( digits + oldCap, 0, oldCap );
delete [] olddigits;
}
BigInt BigInt::operator++()
{
operator+=( 1 );
return *this;
}
BigInt BigInt::operator++( int )
{
return operator++();
}
BigInt BigInt::operator--()
{
operator-=( 1 );
return *this;
}
BigInt BigInt::operator--( int )
{
return operator--();
}
BigInt BigInt::operator-()
{
BigInt result( *this );
result.sign *= -1;
return result;
}
BigInt BigInt::operator+( int n )
{
BigInt result( *this );
result += n;
return result;
}
BigInt BigInt::operator+( BigInt n )
{
BigInt result( *this );
result += n;
return result;
}
BigInt &BigInt::operator+=( int n )
{
if( size == capacity ) grow();
int nsign = sig( n );
if( !nsign ) return *this;
if( !sign ) sign = nsign;
if( sign == nsign )
{
n *= nsign;
int carry = 0;
int i;
for( i = 0; n || carry; i++ )
{
int dig = n % 10;
int newdig = digits[i] + dig + carry;
digits[i] = newdig % 10;
carry = newdig / 10;
n /= 10;
}
size = max( i, size );
}
else operator-=( -n );
return *this;
}
BigInt &BigInt::operator+=( BigInt n )
{
int maxS = max( size, n.size ) + 1;
while( maxS >= capacity ) grow(); //FIXME: this is stupid
if( !n.sign ) return *this;
if( !sign ) sign = n.sign;
if( sign == n.sign )
{
int carry = 0;
int i;
for( i = 0; i < maxS - 1 || carry; i++ )
{
int newdig = carry;
if( i < size ) newdig += digits[i];
if( i < n.size ) newdig += n.digits[i];
digits[i] = newdig % 10;
carry = newdig / 10;
}
size = max( i, size );
}
else
{
n.sign *= -1;
operator-=( n );
n.sign *= -1;
}
return *this;
}
BigInt BigInt::operator-( int n )
{
BigInt result( *this );
result -= n;
return result;
}
BigInt BigInt::operator-( BigInt n )
{
BigInt result( *this );
result -= n;
return result;
}
BigInt &BigInt::operator-=( int n )
{
if( size == capacity ) grow();
int nsign = sig( n );
if( !nsign ) return *this;
if( !sign ) sign = 1;
if( sign == nsign )
{
BigInt bin = n;
if( sign >= 0 && *this < bin || sign < 0 && *this > bin )
{
// Subtracting a bigger number
operator=( toInt() - n );
return *this;
}
n *= nsign;
int carry = 0;
int i;
for( i = 0; n || carry; i++ )
{
int dig = n % 10;
int newdig = digits[i] - dig + carry;
if( newdig < 0 ) newdig += 10, carry = -1;
else carry = 0;
digits[i] = newdig;
n /= 10;
}
normalize();
}
else operator+=( -n );
return *this;
}
BigInt &BigInt::operator-=( BigInt n )
{
int maxS = max( size, n.size ) + 1;
while( maxS >= capacity ) grow(); //FIXME: this is stupid
if( !n.sign ) return *this;
if( !sign ) sign = 1;
if( sign == n.sign )
{
if( sign >= 0 && *this < n || sign < 0 && *this > n )
{
// Subtracting a bigger number
BigInt tmp = n;
tmp -= *this;
*this = tmp;
sign = -sign;
return *this;
}
int carry = 0;
int i;
for( i = 0; i < maxS - 1; i++ )
{
int newdig = carry;
if( i < size ) newdig += digits[i];
if( i < n.size ) newdig -= n.digits[i];
if( newdig < 0 ) newdig += 10, carry = -1;
else carry = 0;
digits[i] = newdig;
}
if( carry ) // Subtracted a bigger number, need to flip sign
{
if( i ) digits[0] = 10 - digits[0];
size = ( i ? 1 : 0 );
for( int j = 1; j < i; j++ )
{
digits[j] = 9 - digits[j];
if( digits[i] ) size = j + 1;
}
sign *= -1;
}
normalize();
}
else
{
n.sign *= -1;
operator+=( n );
n.sign *= -1;
}
return *this;
}
BigInt BigInt::operator*( int n )
{
BigInt result( 0, size + ( int )sizeof( n ) * 8 );
int nsign = sig( n );
n *= nsign;
result.sign = sign * nsign;
if( !result.sign ) return result;
int i, j;
for( i = 0; n; i++ )
{
int dig = n % 10;
if( dig )
{
int carry = 0;
for( j = 0; j < size || carry; j++ )
{
int newDig = result.digits[i + j] + ( j < size ? dig * digits[j] : 0 ) + carry;
result.digits[i + j] = newDig % 10;
carry = newDig / 10;
}
}
n /= 10;
}
result.size = i + j - 1;
return result;
}
BigInt BigInt::operator*( BigInt n )
{
BigInt result( 0, size + n.size );
result.sign = sign * n.sign;
if( !result.sign ) return result;
int i, j;
for( i = 0; i < n.size; i++ )
{
if( n.digits[i] )
{
int carry = 0;
for( j = 0; j < size || carry; j++ )
{
int newDig =
result.digits[i + j] +
( j < size ? n.digits[i] * digits[j] : 0 ) +
carry;
result.digits[i + j] = newDig % 10;
carry = newDig / 10;
}
}
}
result.size = i + j - 1;
return result;
}
void BigInt::operator*=( int n )
{
operator=( operator*( n ) );
}
void BigInt::operator*=( BigInt n )
{
operator=( operator*( n ) );
}
BigInt BigInt::operator/( int n )
{
if( !n ) n /= n; //XXX: force a crash
BigInt result( *this );
result /= n;
return result;
}
BigInt BigInt::operator/( BigInt n )
{
if( !n ) n.size /= n.size; //XXX: force a crash
BigInt result( *this );
result /= n;
return result;
}
void BigInt::operator/=( int n )
{
divide( n );
}
void BigInt::operator/=( BigInt n )
{
divide( n );
}
int BigInt::operator%( int n )
{
BigInt tmp( *this );
return tmp.divide( n );
}
void BigInt::operator%=( int n )
{
operator=( divide( n ) );
}
BigInt BigInt::operator%( BigInt n )
{
BigInt tmp( *this );
return tmp.divide( n );
}
void BigInt::operator%=( BigInt n )
{
operator=( divide( n ) );
}
int BigInt::divide( int n )
{
if( !n ) n /= n; //XXX: force a crash
int nsign = sig( n );
n *= nsign;
if( !sign ) return 0;
sign *= nsign;
int tmp = 0;
for( int i = size - 1; i >= 0; i-- )
{
tmp *= 10;
tmp += digits[i];
digits[i] = tmp / n;
tmp -= digits[i] * n;
}
normalize();
return tmp;
}
BigInt BigInt::divide( BigInt n )
{
if( !n ) n.size /= n.size; //XXX: force a crash
if( !sign ) return 0;
sign *= n.sign;
int oldSign = n.sign;
n.sign = 1;
BigInt tmp( 0, size );
for( int i = size - 1; i >= 0; i-- )
{
tmp *= 10;
tmp += digits[i];
digits[i] = 0;
while( tmp >= n ) { tmp -= n; digits[i]++; }
}
normalize();
n.sign = oldSign;
return tmp;
}
// This is only exact to the first 15 or so digits, but it is
// never an over-estimate
BigInt BigInt::operator*( long double n )
{
// the number of digits after the decimal point to use
int DIGS_AFTER_DOT = 15;
int nsign = sig( n );
n *= nsign;
int ndigs = n >= 1 ? ( int )log10( n ) + 1 : 0;
BigInt result( 0, size + ndigs );
result.sign = sign * nsign;
if( !result.sign ) return result;
if( n >= 1 ) for( int i = 0; i < ndigs; i++ ) n /= 10;
result.size = 0;
char afterDot[DIGS_AFTER_DOT + 1];
memset( afterDot, 0, sizeof( afterDot ) );
// Keep going until the DIGS_AFTER_DOT'th digit after the decimal point
for( int i = ndigs - 1; i >= -DIGS_AFTER_DOT; i-- )
{
n *= 10;
int dig = ( int )floor( n );
n -= dig;
if( !dig ) continue;
int carry = 0;
for( int j = 0; j < size || carry; j++ )
{
int newdig =
( i + j < 0 ? afterDot[-( i + j )] : result.digits[i + j] )
+ dig * digits[j]
+ carry;
( i + j < 0 ? afterDot[-( i + j )] : result.digits[i + j] ) = newdig % 10;
if( i + j >= 0 && result.digits[i + j] ) result.size = max(result.size, i + j + 1);
carry = newdig / 10;
}
}
if( !result.size ) result.sign = 0;
return result;
}
void BigInt::operator*=( long double n )
{
operator=( operator*( n ) );
}
BigInt BigInt::operator<<( int n )
{
BigInt result( *this );
result <<= n;
return result;
}
void BigInt::operator<<=( int n )
{
if( n < 0 ) operator>>=( -n );
else if( n > 0 )
{
BigInt mult( 1, 4 * n );
for( int i = ( 1 << 30 ); i; i >>= 1 )
{
mult *= mult;
if( n & i ) mult *= 2;
}
operator*=( mult );
}
}
BigInt BigInt::operator>>( int n )
{
BigInt result( *this );
result >>= n;
return result;
}
void BigInt::operator>>=( int n )
{
if( n < 0 ) operator<<=( -n );
else if( n > 0 )
{
BigInt mult( 1, 4 * n );
for( int i = ( 1 << 30 ); i; i >>= 1 )
{
mult *= mult;
if( n & i ) mult *= 2;
}
operator/=( mult );
}
}
/*
BigInt BigInt::operator&( int n )
{
}
BigInt BigInt::operator&( BigInt n )
{
}
void BigInt::operator&=( int n )
{
}
void BigInt::operator&=( BigInt n )
{
}
BigInt BigInt::operator|( int n )
{
}
BigInt BigInt::operator|( BigInt n )
{
}
void BigInt::operator|=( int n )
{
}
void BigInt::operator|=( BigInt n )
{
}
BigInt BigInt::operator^( int n )
{
}
BigInt BigInt::operator^( BigInt n )
{
}
void BigInt::operator^=( int n )
{
}
void BigInt::operator^=( BigInt n )
{
}
BigInt BigInt::operator~()
{
}
*/
BigInt BigInt::operator,( int n )
{
BigInt result( 0, size + ( int )sizeof( n ) * 8 );
for( result.size = 0; n; result.size++ )
{
result.digits[result.size] = n % 10;
n /= 10;
}
memcpy( result.digits + result.size, digits, size * sizeof( digits[0] ) );
result.size += size;
result.sign = 1;
result.normalize();
return result;
}
BigInt BigInt::operator,( BigInt n )
{
BigInt result( 0, size + n.size );
memcpy( result.digits, n.digits, n.size * sizeof( n.digits[0] ) );
memcpy( result.digits + n.size, digits, size * sizeof( digits[0] ) );
result.size = size + n.size;
result.sign = 1;
result.normalize();
return result;
}
bool BigInt::operator!()
{
return !size;
}
BigInt::operator bool()
{
return size;
}
//BigInt::operator int()
//{
// return toInt();
//}
BigInt::operator string()
{
return toString();
}
bool BigInt::operator<( BigInt n )
{
return( compare( n ) < 0 );
}
bool BigInt::operator>( BigInt n )
{
return( compare( n ) > 0 );
}
bool BigInt::operator==( BigInt n )
{
return( compare( n ) == 0 );
}
bool BigInt::operator<=( BigInt n )
{
return( compare( n ) <= 0 );
}
bool BigInt::operator>=( BigInt n )
{
return( compare( n ) >= 0 );
}
bool BigInt::operator<( int n )
{
return( compare( BigInt( n ) ) < 0 );
}
bool BigInt::operator>( int n )
{
return( compare( BigInt( n ) ) > 0 );
}
bool BigInt::operator==( int n )
{
return( compare( BigInt( n ) ) == 0 );
}
bool BigInt::operator<=( int n )
{
return( compare( BigInt( n ) ) <= 0 );
}
bool BigInt::operator>=( int n )
{
return( compare( BigInt( n ) ) >= 0 );
}
int BigInt::compare( BigInt n )
{
if( sign < n.sign ) return -1;
if( sign > n.sign ) return 1;
if( size < n.size ) return -sign;
if( size > n.size ) return sign;
for( int i = size - 1; i >= 0; i-- )
{
if( digits[i] < n.digits[i] ) return -sign;
else if( digits[i] > n.digits[i] ) return sign;
}
return 0;
}
long double log2( BigInt x, long double epsilon = 0.000000000000001 )
{
static /* const */ long double O = 0.0;
if( x.sign <= 0 ) return O / O; // Return NaN
long double y = 0.0, z = 1.0, f = 0.0;
while( x >= 2 )
{
if( x.divide( 2 ) ) f += 1.0;
f /= 2.0;
y++;
}
f += 1.0;
while( z > epsilon )
{
f *= f;
z /= 2.0;
if( f >= 2.0 )
{
y += z;
f /= 2.0;
}
}
return y;
}
inline long double log( BigInt x, long double epsilon = 0.000000000000001 )
{
return log2( x, epsilon ) * 0.6931471805599;
}
inline long double log10( BigInt x, long double epsilon = 0.000000000000001 )
{
return log2( x, epsilon ) * 0.301029995664;
}
inline long double lg( BigInt x, long double epsilon = 0.000000000000001 )
{
return log2( x, epsilon );
}
inline long double ln( BigInt x, long double epsilon = 0.000000000000001 )
{
return log( x, epsilon );
}
int MOD = 1000000007;
BigInt inv(BigInt tar) {
BigInt ret = 1;
for(int i = 30; i >= 0; i--) {
ret = ret * ret % MOD;
if((1ll << i) & (MOD - 2)) ret = ret * tar % MOD;
}
return ret;
}
BigInt func(BigInt c, BigInt x) {
BigInt ret = x * x * x / 3 * -1;
ret = (ret + x * x * c / 2);
ret = (ret + c * x / 2+ x / 3);
if(c * x % 2 > 0) ret += 1;
return ret;
}
BigInt GCD(BigInt a, BigInt b) {
if(a < b) return GCD(b, a);
if(b == 0) return a;
return GCD(b, a % b);
}
int main(void) {
string _h, _w;
cin >> _h >> _w;
BigInt h(_h), w(_w);
BigInt xsum = func(w, w);
BigInt ysum = func(h, h);
BigInt ans = xsum * ysum * 9;
BigInt cases = w * (w + 1) / 2;
cases = cases * (h * (h + 1) / 2);
BigInt gv = GCD(ans, cases);
ans = ans / gv;
cases = cases / gv;
cases %= BigInt("1000000007");
cout << ans * inv(cases) % BigInt("1000000007");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 22 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 23 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 25 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 28 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 29 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 30 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 31 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 32 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 33 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 34 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 35 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 36 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 37 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 38 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 39 |
Correct |
0 ms |
1880 KB |
Output is correct |
| 40 |
Correct |
0 ms |
1880 KB |
Output is correct |
