CODE:

#include "modular.h"
#include 

using namespace Modular;
using namespace std;
int main(){
	
	cout  a( 5 );
	cout (a)  b( 8 );
	cout (b) ( a + b ) ( a - b ) ( a * b ) ( b ^ 40000000000000000ULL ) 

using namespace Modular;
using namespace std;

//なんか大きな数を定義
static const unsigned long long BIG_NUM = ( ULLONG_MAX - 345);

int main(){
	cout  c( BIG_NUM - 11 );
	cout (c)  d( BIG_NUM - 111 );
	cout (d) ( c + d ) ( c - d ) ( c * d ) ( c ^ 1000000000000000ULL ) 
#include 
#include 
#include 
#include 


namespace Modular{

	namespace Private
	{

		//numeric_limitが constexprに対応していないので、それに対処する
		template
		struct Max;

		//Typeのビット数を求める
		template
		struct Bit{
			//Bitすうを求めるコア関数
			template
			struct CalculateBit
			{
				enum
				{
					value = ( CalculateBit> 1) >::value ) + 1
				};
			};

			template 
			struct CalculateBit
			{
				enum{ value = 0 };
			};

			//ビット数
			enum{ 
				value = CalculateBit::value>::value, 
			};

			//最大の桁のビットのみがONの時の値
			static const Type leftMost = ( static_cast(1) 
		struct Max
		{
			static const unsigned long value = ULONG_MAX;
		};
		
		template 
		struct Max
		{
			static const unsigned long long value = ULLONG_MAX;
		};

		template
		struct Max
		{
			static const unsigned short value = USHRT_MAX;
		};


		//Aのビット長はBのビット長の2倍以上か？
		template
		struct HasMoreBitsThanTwice
		{
			enum{ value = ( Bit::value >= Bit::value*2) };  
		};

		//ある定数が与えられたとき、それを格納するのに最も適した型を選択する
		template
		struct ChooseValueType
		{
			typedef typename boost::mpl::if_c::value ::type type;
		};

		//ある定数とその型が与えられたとき、その定数未満の数の加算がオーバーフローするかどうかを判断する
		template
		struct HaveToChangeAddAlgorithm
		{
			enum{ value = ( Num > (Max::value / 2 +1 ) ) };
		};

		//何もしないメタ関数
		template
		struct DoNothing
		{
			typedef Type type;
		};

		//乗算の型としてもっとも適切なものを選択する
		template
		struct ChooseOnMultiplicationType
		{
			/*
				ビット数をnとして
				
				① Num 

				② Num 

				③ Num 
			*/
			typedef 
				boost::mpl::if_c::value,
					DoNothing,
					boost::mpl::if_c::value,
						unsigned long long,
						std::pair
					>
				>
				Pattern1;

			typedef
				DoNothing::value,
						unsigned long long,
						std::pair
					>
				>
				Pattern2;

			typedef
				DoNothing
					>
				>
				Pattern3;

			typedef typename
				boost::mpl::if_c::value,
					DoNothing,
					boost::mpl::if_c::value,
						Pattern2,
						Pattern3
					>
				>::type::type::type::type type;
		};

		//ある型の最大値＋１をNでわった値をを求める
		template
		struct CalculateMaxPlus1_ModNum
		{
			static const Type value = ( ( (Max::value%Num) + 1 ) % Num );
		};
		

		//modクラスのコア。基本的にこいつが本体で、modクラスはただのラッパー
		template 
		struct ModCore{
			//それぞれ、加算をどうするかと、乗算をどうするかの結果（掛け算の方はインスタンス化しない、複雑だから）
			typedef typename ChooseOnMultiplicationType::type	MType;
			typedef typename HaveToChangeAddAlgorithm		AType;

			//自身の名前が長いので、省略。
			typedef ModCore ModCore_;

			//加算のアルゴリズム
			template 
			struct Add;

			//アルゴリズムに手を加えない場合
			template 
			struct Add
			{
				static inline void Do( ModCore_& lhs, ModCore_& rhs )
				{
					lhs.value_ = ( lhs.value_ + rhs.value_ ) % NMax;
				}
			};

			//アルゴリズムに手を加える場合
			template 
			struct Add
			{
				static inline void Do( ModCore_& lhs, ModCore_& rhs )
				{
					//格納している値の型の最大値を考え、最大値までの残りを考える
					Type surplus = Max::value - lhs.value_;

					//残りの数値よりもオペランドの値のほうが大きい、つまりオーバーフローしてしまう場合は対処する
					if( rhs.value_  より　a + b > limits ⇒　a + b > Nmax　が成り立つ。
						//よって、a + b は　 b - ( n - a ) を計算することにより循環せずに求まる
						lhs.value_ = rhs.value_ - ( NMax - lhs.value_ );
					}
				}
			};


			//乗算のアルゴリズム
			template
			struct Multiply;

			//オーバーフローの心配がない場合
			template
			struct Multiply
			{
				static inline void Do( ModCore_& lhs, ModCore_& rhs )
				{
					MType lhsv = lhs.value_;
					MType rhsv = rhs.value_;

					lhs.value_ = (lhsv*rhsv) % NMax;
				}
			};

			//オーバーフローの心配がある場合
			template
			struct Multiply
			{
				static void Do( ModCore_& lhs, ModCore_& rhs )
				{
					Type lhsv = lhs.value_;
					Type rhsv = rhs.value_;

					int lhsBits = CalcBits( lhsv );
					int rhsBits = CalcBits( rhsv );
	
					if( lhsv ( Bit::value );
					//あふれるビットがなければ
					if( overflow >= (Bit::value - i); 
								//上の桁へ加える
								temp.first += rhsv_inForHigh;
							}

							//下の桁を足し合わせるときには注意があり、もし上の桁へ繰り上がる場合は上の桁へ1足してやらねばならない。
							//また、加算時にオーバーフローする可能性があるので、最高の桁のビットがONのばあいはいったんOFFにして計算し、
							//あとで戻してやることにする

							//下の桁の最高位のビットがONの場合は保存してOFFに
							bool isLeftMostBitOfLhsOn = ( temp.second & Bit::leftMost ) != 0;
							if( isLeftMostBitOfLhsOn )  temp.second -= Bit::leftMost;

							//加える側の最高位のビットがONの場合は保存してOFFに
							bool isLeftMostBitOfRhsOn = ( rhsv_inForLow & Bit::leftMost ) != 0;
							if( isLeftMostBitOfRhsOn ){
								rhsv_inForLow -= Bit::leftMost;
							}

							//オーバーフローの起こらない加算
							temp.second += rhsv_inForLow;
							
							//減らした分を加えて元に戻す
							if( temp.second & Bit::leftMost )
							{
								if( isLeftMostBitOfLhsOn && isLeftMostBitOfRhsOn )
									++temp.first;											//1+1+1 = 11 (一つ繰り上がり)
								else if( isLeftMostBitOfLhsOn || isLeftMostBitOfRhsOn )
									++temp.first, temp.second -= Bit::leftMost;		//1+0+1 or 1+1+0= 10 
																							//(一つ繰り上がりし、現在立っているビットを元に戻す)
							}
							else
							{
								if( isLeftMostBitOfLhsOn && isLeftMostBitOfRhsOn )			// 0+1+1 = 10(繰り上がり)
									++temp.first;
								else if( isLeftMostBitOfLhsOn || isLeftMostBitOfRhsOn )
									temp.second += Bit::leftMost;						//0+1+0 or 0+0+1 = 01(繰り上がりなし)
							}
						}
					}
					
					//この時点でtempにはlhs*rhsの結果が格納されている
					//上位桁の剰余を求める
					bit = 1;

					//まず、上の桁の一桁目の剰余を出す
					ModCore_ poweredTwo( CalculateMaxPlus1_ModNum::value );

					//計算結果を格納する変数
					ModCore_ Mod_HighValue(0);


					for( int i = 0; i  0; ++count ) Num >>= 1;
					return count;
				}
			};



			//実際に格納している変数はこれだけである（unsigned long もしくは　unsigned lon long のいずれか）
			Type value_;
		public:
			ModCore ( const ModCore_& other )
				:value_( other.value_ )
			{
			}

			ModCore_& operator = ( ModCore_ other )
			{
				value_ = other.value_;
				return *this;
			}

			explicit ModCore( Type other )
				:value_( other % NMax )
			{
			}

			ModCore_& operator += ( ModCore_ other )
			{
				Add::Do( *this, other );
				return *this;
			}

			ModCore_& operator -= ( ModCore_ other )
			{	
				//合同式においては、減算は加算に置き換えることができる
				return operator += ( ModCore_( NMax - other.value_ ) );
			}


			ModCore_& operator *= ( ModCore_ other )
			{
				Multiply::value >::Do( *this, other );
				return *this;
			}


			//n乗を求める
			template
			ModCore_& operator ^= ( NType nth_power )
			{
				//なぜsatatic_assertはVSだと日本語が文字化けするんだｗ
				static_assert( std::is_unsigned::value , "You can only use unsigned-types with a mod-type in operator ^=" );
				if( nth_power == 0 )
				{
					value_ = 1;
				}
				//ある程度の数までは普通に計算したほうが速い。
				else if( nth_power  1);

					/*
					補足
					たとえば 2^3なら、2に2を3回かけてやればいい。
					しかし
					a = 2として
					a^7ならaを６回かけるよりも
					temp = aとして


					//a *= temp←この計算はしない
					temp = temp^2

					a *= temp;
					temp = temp^2;

					a *= temp
					とした方が早い

					これは　6 = 0b110のビットが立っている部分だけ計算するということに他ならない
					この方法はa^nを求める手法として計算量は最小ではないが、少なくともlogn程度に収まる
					*/

				} 
				return *this;
			}

			bool operator == ( ModCore_ other )
			{
				return value_ == other.value_;
			}
		};
	}



	template 
	class mod:
		public boost::operators >
	{
		typedef typename Private::ChooseValueType::type type;
		
		Private::ModCore::value
		> value_;

		typedef mod Mod;
			
		template
		friend Type modular_cast( const Mod& );

	public:
		mod()
			:value_(0)
		{
		}
			
		explicit mod( type init )
			:value_( init )
		{
		}

		Mod& operator = ( const Mod& other )
		{
			value_ = other.value_;
			return *this;
		}

		Mod& operator += ( const Mod& other )
		{
			value_ += other.value_;
			return *this;
		}

		Mod& operator -= ( const Mod& other )
		{
			value_ -= other.value_;
			return *this;
		}

		Mod& operator *= ( const Mod& other )
		{
			value_ *= other.value_;
			return *this;
		}

		template
		Mod& operator ^= ( const NType& other )
		{
			value_ ^= other;
			return *this;
		}

		Mod& operator == ( const Mod& other )
		{
			return value_ == other.value_;
		}

		template
		const Mod operator ^ ( const NType& other )
		{
			Mod temp = *this;
			temp ^= other;
			return temp;
		}
	};

	template
	Type modular_cast( const mod& m )
	{
		return static_cast(m.value_.value_);
	}
}