kmjp's blog

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

Codeforces #512 Div1 D. Linear Congruential Generator

問題設定がややこしい…。
http://codeforces.com/contest/1053/problem/D

問題

N要素の整数列Aがあったとする。
N個の線形変換を行う関数f_i(x) = (a_i * x + b_i) mod p_iを考える。
Aのi番目の要素にf_i(x)を適用する、ということを全要素に行い、新たな数列を作ることを考える。

ここで、p_iがすべて与えられており、整数列の初期値およびa_iとb_iを任意に選べるとする。
p_iが素数である時、Aの最長周期はいくつになるか。

解法

各要素iに対し初期値・a_i・b_iを適切に設定した場合、周期をC(i)、周期的なパターンに入るまでの処理回数をP(i)とする。
すると解はmax(P(i)) + LCM(C(i))となる。
ただ、ここでp_iは素数であることから、取りえる値は以下のいずれかである。

  1. C(i)=p_iかつP(i)=0
  2. C(i)=p_i-1かつP(i)=0
  3. C(i)=1かつP(i)=1

P(i)は0か1なので解に対する寄与が小さいため、基本的にはP(i)=0でLCMが大きくなるC(i)を選ぶ戦略で行こう。
LCMを考えるにあたり、各素因数の次数を大きく保てるようにしよう。
C(i)=p_iのケースではp_iが素数なので簡単だが、C(i)=p_i-1のケースでは大抵C(i)が合成数になる点に注意が必要。

以下素因数pの大きい順に見ていく。

  • C(i)を素因数分解したとき、その次数の最大値がC(i)=p_i-1の形をしたものに由来している場合:
    • 同じC(i)=p_i=pの形のものがあれば、これらはC(i)=p_i-1の形にした方がLCMが稼げるのでそうする。
    • C(i)=p_i-1の形のものが2つ以上あれば、その項目はP(i)=1とする。
  • C(i)を素因数分解したとき、その次数の最大値がC(i)=p_iの形をしたものに由来している場合:
    • 同じC(i)=p_i=pの形のものが2つ以上あれば、これらはC(i)=p_i-1の形にした方がLCMが稼げるのでそうする。
const int prime_max = 2100000;
int NP,prime[200000],divp[prime_max];
map<int,int> fp[2020202];
int add;
void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime[NP++]=i;
		divp[i]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

int N;
int P[202020],step[202020];
map<int,int> C[2020202];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	for(i=2;i<=2000000;i++) {
		x=i;
		while(x>1) {
			fp[i][divp[x]]++;
			x/=divp[x];
		}
	}
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	sort(P,P+N);
	reverse(P,P+N);
	
	FOR(i,N) {
		if(C[P[i]].empty()) {
			C[P[i]][1]=1;
		}
		else {
			step[i]=1;
			P[i]--;
			FORR(f,fp[P[i]]) C[f.first][f.second]++;
		}
	}
	FOR(i,N) {
		if(step[i]==0) {
			if(C[P[i]][1]>1 || C[P[i]].rbegin()->first>1) {
				C[P[i]][1]--;
				if(--C[P[i]][1]==0) C[P[i]].erase(1);
				step[i]=2;
				assert(1);
			}
		}
		else {
			int rem=0;
			FORR(f,fp[P[i]]) {
				if(C[f.first][f.second]==1 && C[f.first].rbegin()->first==f.second) rem=1;
			}
			if(rem==0) {
				FORR(f,fp[P[i]]) {
					if(--C[f.first][f.second]==0) C[f.first].erase(f.second);
				}
				add=1;
			}
		}
	}
	
	ll ret=1;
	for(i=1;i<=2000000;i++) if(C[i].size()) {
		FOR(x,C[i].rbegin()->first) ret=ret*i%mo;
	}
	
	cout<<(ret+add)%mo<<endl;
	
}

まとめ

考察もややこしいし、計算量見積もりパートも大変。
周期がp_i-1になるケースがあるのは覚えておかないとな。