TopCoder SRM 840 : Div1 Hard MaximizeValue

手間取ったけど何とか解けた。
https://community.topcoder.com/stat?c=problem_statement&pm=17877&rd=19471

問題

奇素数Pと、正整数Kが与えられる。
N=2*P^Kとする。
ここで0～(N-1)番の部屋があり、i番の部屋にはi個のコインがある。

今プレイヤーが1番の部屋にいる。
この状態で任意の整数Sを選び、「今いる部屋xに対し、(x*S)%N番の部屋に移動する」という作業を繰り替えす。
その際、移動先の部屋のコインを回収する。最終的に1番の部屋に戻れた場合、作業を終了する。

作業を終了でき、かつ回収するコイン数が最大となるSを1つ求めよ。

解法

位数がφ(N)となるような値をSに選べばよい。
Nと互いに素なSを、3,5,7,....と順に探していけばすぐに見つかる。
位数がφ(N)になるかどうかは、φ(N)未満のφ(N)の約数dに対し、S^d=1 (mod N)となるものがないことを示せばよい。

ll mo;
ll T;

__int128 modpow(__int128 a, ll n = mo-2) {
	__int128 r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=2;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}

class MaximizeValue {
	public:
	
	long long solve(long long P, int K) {
		ll N=2;
		int i;
		FOR(i,K) N*=P;
		
		mo=N;
		T=N/2/P*(P-1);
		
		vector<ll> cand=enumdiv(T);
		ll ma=0,ret=0;
		cout<<N<<endl;
		for(i=2;i<=min(10000LL,N);i++) if(__gcd((ll)i,N)==1) {
			int ok=1;
			FORR(c,cand) {
				if(modpow(i,c)==1) {
					ok=0;
					break;
				}
			}
			cout<<i<<" "<<ok<<endl;
			if(ok) return i;
		}
		return ret;
	}
}

まとめ

本番は離散対数を求めようとしてしまい、解は合うけどS1つ試すのに2秒ぐらいかかってしまってタイムロスした。