yukicoder No.403 2^2^2

フェルマーの小定理を使ってpowmodするだけ
……と見せかけて、「AがPの倍数かつBがP-1の倍数」に気をつける必要がある
（剰余をとってから累乗を計算すると0^0となるが、0を返すのか1を返すのか）

先日ライブラリ化したpowmodの最後をちょこっといじって0^0で0を返すようにして、あとはただ計算するだけ

typedef long long ll;
P=1e9+7;
ll a,b,c;
ll pom(ll a,ll i,ll m){return i?i%2?pom((a%m)*(a%m),i/2,m)*a%m:pom((a%m)*(a%m),i/2,m)%m:!!a;}
int main(){
	scanf("%lld%*c%lld%*c%lld",&a,&b,&c);
	a=!printf("%lld %lld",pom(pom(a,b,P),c,P),pom(a,pom(b,c,P-1),P));
}

とりあえず自明な短縮をして

P=1e9+7,x;
long a,b,c;
p(long a,long i,int m){x=i?p(a*a%m,i/2,m)*(i%2?a:1)%m:!!a;}
main(){
	scanf("%ld^%ld^%ld",&a,&b,&c);
	a=!printf("%ld %ld",p(a,c%~-P*b,P),p(a%=P,p(b%=P-1,c,P-1),P));
}

Pを1e9+7ではなく1e9+6にすれば、出力部分が

p(a,c%~-P*b,P),p(a%=P,p(b%=P-1,c,P-1),P)
p(a,c%P*b,~P),p(a%=~P,p(b%=P,c,P),~P)

となり縮む。まとめると

P=1e9+6,x;
long a,b,c;
p(long a,long i,int m){x=i?p(a*a%m,i/2,m)*(i%2?a:1)%m:!!a;}
main(){
scanf("%ld^%ld^%ld",&a,&b,&c);
a=!printf("%d %d",p(a,c%P*b,~P),p(a%=~P,p(b%=P,c,P),~P));
}

175B
さて、powmodの引数をintにして宣言を省略したい。
そのためにネックとなるがp(b,c,P-1)なのだけど

P=1e9+6,x;
long a,b,c;
p(a,i,m){x=i?p(1L*a*a%m,i/2,m)*1L*(i%2?a:1)%m:!!a;}
main(){
	scanf("%ld^%ld^%ld",&a,&b,&c);
	a=!printf("%d %d",p(a,c%P*b,~P),p(a%=~P,p(b%=P,c%(~-P/2),P),~P));
}

となりむしろ伸びる（φ(1e9+6)=5e8+2）
（確認してないがこれで多分通るはず）

メモ

yukicoderでゆるふわgolf

yukicoder No.403 2^2^2