• 欢迎光临~

# [Ynoi2016] 炸脖龙 I

(a^b≡a^{bmod varphi(p)+varphi(p)×[b≥ϕ(p)]} (text{mod} p))

1. (text{mod})(1) 时，此时不管是什么数都是 (0)

2. 底数 (text{a})(1) 时，不管多少幂都是 (1)

3. 递归到底时再判断是否需要加上 (varphi(p)) 即可。

4. 多取点模，这题不卡常！！1

### Code:

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <bitset>
#define int long long
using namespace std;
char ch=getchar();int x=0, f=1;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int INF=0x3f3f3f3f;
const int N=(int)(500005);
const int M=(int)(20000005);
struct BIT{
#define lowbit(x) (x&(-x))
int sum[N];
void add(int x, int y){if(!y) return ;for(; x<N; x+=lowbit(x)) sum[x]+=y;}
int query(int x){int ret=0;for(; x>0; x-=lowbit(x)) ret+=sum[x];return ret;}
}bit;
struct node{int v;bool flg;};
node ksm(int a, int b, int mo){
node ret=(node){1, 0};
int tmp=a%mo;if(a>=mo) ret.flg=true, ret.v%=mo;
while(b){
if(b&1) ret.v*=tmp;
if(ret.v>=mo) ret.flg=true, ret.v%=mo;
tmp*=tmp;
if((b/2)&&tmp>=mo) ret.flg=1, tmp%=mo;
b>>=1;
}
return ret;
}
int n, m, phi[M], st[M], tot, a[N];
bitset <M> u;
void pre(int lim=20000000){
phi[1]=1;
for(int i=2; i<=lim; i++){
if(!u[i]) st[++tot]=i, phi[i]=i-1;
for(int j=1; j<=tot&&i*st[j]<=lim; j++){
u[i*st[j]]=1;
if(i%st[j]==0){phi[i*st[j]]=phi[i]*st[j];break;}
phi[i*st[j]]=phi[i]*(st[j]-1);
}
}
}
node solve(int l, int r, int p){
int tmp=bit.query(l);//printf("--%d %d %lld %lldn", l, r, tmp, p);
if(p==1) return (node){0, 1};
if(l==r) return tmp>=p?(node){tmp%p, 1}:(node){tmp, 0};
if(tmp==1) return (node){1, 0};
node mi=solve(l+1, r, phi[p]);
if(mi.flg) mi.v+=phi[p];
return ksm(tmp, mi.v, p);
}
signed main(){