kmjp's blog

競技プログラミング参加記です

Codeforces #210 Div1 D. Levko and Sets

これは自力じゃあ解けないなぁ。
http://codeforces.com/contest/360/problem/D

問題

素数pと、2つの整数列A[i],B[i]が与えられる。

ここからN個の整数集合S[i]を作る。
整数の集合S[i]は初期状態で1だけを持つ。
S[i]に変化がなくなるまで、以下の処理を繰り返す。

  • S[i]中の各要素cに対し、(c*(A[i]^B[j]) mod p)を求め、その値がSに含まれていなかったら追加する。

最終的に、どれか1つ以上のS[i]に含まれる整数の数を求めよ。

解法

S[i]に含まれる整数がどんなものか考える。
適当な原始元gを仮定すると、A[i]≡g^r[i] (mod p)と置くことができる。
よって、S[i]中の要素は結局 g^{r_i \times \sum_j (B_j*C_j)} (C[j]は任意の整数)で表現できる数値に限られる。
フェルマーの小定理より、そのような要素数は(p-1)/GCD(r[i],各B[j],p-1)となることがわかる。

あとは包除定理の要領で、どこか1つ以上の要素に含まれる整数の数を数え上げればよい。

int N,M,P;
ll A[100001];
map<ll,int> ndiv;
ll ret;

set<ll> enumdiv(ll n) {
	set<ll> S;
	for(ll i=1;i*i<=n;i++) if(n%i==0) S.insert(i),S.insert(n/i); 
	return S;
}
ll modpow(ll a, ll n, ll mo) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>P;
	FOR(i,N) cin>>A[i];
	y=P-1;
	FOR(i,M) cin>>x, y=__gcd(y,x+(P-1));
	set<ll> div=enumdiv(P-1);
	
	FOR(i,N) {
		ITR(it,div) if(modpow(A[i],y*(*it),P)==1) {
			ndiv[(P-1)/(*it)]=0;
			break;
		}
	}
	for(map<ll,int>::reverse_iterator rit=ndiv.rbegin();rit!=ndiv.rend();rit++) {
		rit->second=(P-1)/rit->first;
		ITR(it,ndiv) if(it->first>rit->first && it->first%rit->first==0) rit->second-=it->second;
		ret+=rit->second;
	}
	cout<<ret<<endl;
}

まとめ

前半のGCDに持って行く部分も、後半の包除原理にもっていく過程も自力じゃすんなり書けそうにないな。