yukicoder : No.1411 Hundreds of Conditions Sequences

数学問が続くなぁ…。
https://yukicoder.me/problems/no/1411

問題

整数列Aが与えられる。
要素1つ除いた数列Bに対し、以下を満たす数列Cの組み合わせを答えよ。

• 0≦C[i]＜B[i]
• |C[i]-C[j]| ≡ 0 (mod GCD(B[i],B[j]))でない(i,j)の組がある

解法

C[i]-C[j]

≡ 0 (mod GCD(B[i],B[j]))を全(i,j)が満たす条件は、C[i] mod B[i]が各iについて一致することである。

これを満たすC[i]の組み合わせは、LCM(B)通りである。

よって、Prod(B)-LCM(B)を答えよう。
元の整数列Aについてそれぞれの要素を素因数分解しておき、各素因数の乗数を上位2位まで計算しておくと、1要素除いたLCM(B)が高速に計算できる。

const int prime_max = 1000000;
vector<int> prime;
int NP,divp[prime_max];
const ll mo=1000000007;

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

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

int N,A[101010];
map<int,int> P[1010100];
vector<pair<int,int>> Ps[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,1000010) Ps[i].push_back({1,-1});
	cprime();
	cin>>N;
	ll prod=1;
	FOR(i,N) {
		cin>>A[i];
		x=A[i];
		FORR(c,prime) {
			if(c*c>x) break;
			if(x%c==0) {
				ll a=1;
				P[i][c]=1;
				while(x%c==0) P[i][c]*=c, x/=c;
				Ps[c].push_back({P[i][c],i});
			}
		}
		if(x>1) {
			P[i][x]=x;
			Ps[x].push_back({P[i][x],i});
		}
		prod=prod*A[i]%mo;
	}
	
	ll lcm=1;
	FOR(i,1000001) {
		sort(ALL(Ps[i]));
		lcm=lcm*Ps[i].back().first%mo;
	}
	FOR(i,N) {
		prod=prod*modpow(A[i])%mo;
		ll lcm2=lcm;
		FORR2(c,n,P[i]) {
			if(Ps[c].back().second==i) {
				lcm2=lcm2*modpow(n)%mo*Ps[c][Ps[c].size()-2].first%mo;
			}
		}
		cout<<(prod+mo-lcm2)%mo<<endl;
		prod=prod*A[i]%mo;
	}
	
}

まとめ

この式変形、シンプルな内容なのに初めて見たな。