AOJ 2392: Digit

解法

基本的にはさほど難しくない考察をひたすら続けるだけなので省略.

Wikipediaやuwicoderを見ながら考察する.
ただし、(1+q+q^2+...+q^*)の周期はpより大きくなることがあることに注意する.
再帰するとスタックオーバーフローでREが出るので、TopCoderのスタックサイズの増やし方・改 | システム工房コルンのテクを使うか、ループで解く.

あと下のコードはオフセット周りの場合分けを微妙にミスってると思います.

コード

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef __int128 ll2;
ll N, M, L;

#define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));

#define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

ll lcm(ll a, ll b){
	return a/__gcd(a, b)*b;
}

ll lambda(ll m){
	ll res = 1;
	if(m%8==0) m /= 2;
	for(ll i = 2; i*i <= m; i++){
		if(!(m%i)){
			ll r = i-1;
			m /= i;
			while(!(m%i)){
				m /= i;
				r *= i;
			}
			res = lcm(res, r);
		}
	}
	if(m>1) res = lcm(res, m-1);
	return res;
}

ll2 pow_mod2(ll2 a, ll2 r, ll2 m, bool &gt){
	ll2 res = 1;
	while(r){
		if(r&1){
			res *= a;
			if(res >= m) gt = true;
			res %= m;
		}
		r >>= 1;
		a *= a;
		if(r && a >= m) gt = true;
		a %= m;
	}
	return res;
}

ll calc(ll n, ll m){
	if(n<=2) return n;
	if(n==3) return 2*(1+L);
	bool gt = false, gt2;
	if(L%m==0){
		return m+2;
	}
	if(L%m==1){
		ll res = 2*calc(n-1, m);
		if(res >= m) gt = true;
		return res%m+(gt?m:0);
	}
	ll ma = m;
	ll d;
	while((d = __gcd(L, ma)) > 1){
		ma /= d;
	}
	ll phm = lambda(ma);
	ll2 ma2 = (ll2)ma*(ll2)(L-1);
	ll2 m2 = (ll2)m*(ll2)(L-1);
	ll2 b = pow_mod2(L, phm, ma2, gt2);
	b = (b-1+ma2)%ma2;
	b /= ma;
	if(L%ma==1) phm = ma;
	else phm *= __gcd((L-1)/__gcd(L-1, (ll)b), ma);
	if(phm < 40) phm *= 40/phm + 1;
	ll p = calc(n-1, phm);
	ll res = 2*(pow_mod2(L, p, m2, gt)-1+m2)/(L-1);
	if(res >= m) gt = true;
	return res%m+(gt?m:0);
}

int main(){
	BEGIN_STACK_EXTEND(167772160);
	bool dummy;
	int Case = 1;
	while(cin>>N>>M>>L, M){
		printf("Case %d: %lld\n", Case++, N<5?((L-1)*calc(N, M)+1)%M:(2*(ll)pow_mod2(L, calc(N-1, lambda(M)), M, dummy)-1+M)%M);
	}
	END_STACK_EXTEND;
	return 0;
}