yukicoder No.976を解く。

#yukicoder No.976

##問題

正の整数$M$が与えられます。$2^{128}$を$M$で割った余りを求めてください。
入力
$M$
$M$は$1≤M<2^{60}$
を満たす整数です。

出力$M$での余りを出力し、改行してください。

##解く！

a_1 \equiv b_1　(mod　m),a_2 \equiv b_2　(mod　m),...,a_n \equiv b_n　(mod　m)　の時\\
a_1a_2...a_n \equiv b_1b_2...b_n　(mod　m)　であり\\
　\\
a \equiv b　(mod　m),c \equiv ad　(mod　m)の時\\
c \equiv bd　(mod　m)なので\\
　\\
a_1a_2 \equiv b_1b_2　\equiv x_2　(mod　m)\\
a_1a_2a_3 \equiv b_1b_2b_3 \equiv x_2b_3 \equiv x_3　(mod　m)\\
a_1a_2a_3a_4 \equiv b_1b_2b_3b_4 \equiv x_3b_4 \equiv x_4　(mod　m)\\
.\\.\\.\\
a_1a_2a_3...a_n \equiv x_{n-1}b_n　(mod　m)\\

よって以下のコードで解ける。

976.cpp

#include<iostream>
#include<cmath>

#define REP(i,N) for(int i=0,__i=N;i<__i;++i)

typedef unsigned long long ll;

ll M;

bool input(){
	using namespace std;
	cin>>M;
	if(M<1||M>pow(2,60))
		return false;
	return true;
}

ll solve(){
	using namespace std;
	ll res=1;
	REP(i,128){
		res=(res*2)%M;
	}
	return res;
}

int main(){
	using namespace std;
	if(!input())
		return -1;
	ll n=solve();
	cout<<n<<endl;
}

$ echo 1152919305583591425|./a.out
3377698646784256