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

yukicoder No.976を解く。

yukicoder No.976

問題

解く！