問題設定がややこしい…。
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は素数であることから、取りえる値は以下のいずれかである。
- C(i)=p_iかつP(i)=0
- C(i)=p_i-1かつP(i)=0
- 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になるケースがあるのは覚えておかないとな。