题目:

求 $2^x\mod y$ 的值。

输入数据 1

3 3

输出数据 1

2

对于 $100\%$ 的数据：$x<=2^{233333}–1$，$y$ 为 $[3,1000]$ 的质数。

Mine

用的 __int128。

#include<bits/stdc++.h>
#define ll __int128
using namespace std;
ll a,b,m;
ll qread()
{
	ll sum=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {sum=(sum<<1)+(sum<<3)+ch-48;ch=getchar();}
	return sum*f;
}
void qprint(ll x)
{
	if(x>9) qprint(x/10);
	putchar(x%10+48);
	return;
}
void qp(ll x)
{
	if(x<0) x=-x,putchar('-');
	qprint(x);
	return;
}
ll ksm(ll x,ll y,ll MOD)
{
    ll s=1;
    while(y)
    {
        if(y&1) s=s*x%MOD;
        x=x*x%MOD;
        y>>=1;
    }
    return s;
}
int main()
{
    b=qread();
    m=qread();
    a=2;
    //printf("%lld\n",ksm(a,b,m));
    qp(ksm(a,b,m)),putchar('\n');
    return 0;
}