Codeforces ECR #142 : E. Divisors and Table

5問目で割と難しめだった回。
https://codeforces.com/contest/1792/problem/E

問題

整数N,M1,M2が与えられる。
N次正方行列Aは、A(i,j)=i*jとなる。
M=M1×M2に対し、その約数dに対し、f(d)はA中でdが現れる際の行の最小値とする。dがA中に現れない場合f(d)=0とする。

Mの各約数dにおいてf(d)が正のものの個数と、すべてxorを取った値を求めよ。

解法

Mの約数は多くて10^5通り程度なので、約数dを総当たりすることを考える。
d=x*yとなるN以下のx,yのうち最小のxを求める問題であり、言い換えるとyはN以下で極力大きくしたい。
dp(d) := 条件を満たすyの最大値
とする。Mの素因数pに対し、dp(d*p)がどうなるかを適宜求めて行くとよい。

int T;
ll N,M1,M2;
unordered_map<ll,ll> memo;

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=1;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;
}

map<ll,int> enumpr(ll n) {
	map<ll,int> V;
	for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M1>>M2;
		ll M=M1*M2;
		auto P=enumdiv(M1);
		auto Q=enumdiv(M2);
		auto X=enumpr(M1);
		auto Y=enumpr(M2);
		
		vector<ll> A;
		FORR(p,P) FORR(q,Q) A.push_back(p*q);
		sort(ALL(A));
		A.erase(unique(ALL(A)),A.end());
		
		FORR2(a,b,Y) X[a]+=b;
		
		memo.clear();
		int num=0;
		ll val=0;
		FORR(a,A) {
			if(a<=N) memo[a]=a;
			if(a/memo[a]<=N) {
				num++;
				val^=a/memo[a];
			}
			FORR2(p,q,X) {
				if(M/a%p==0) {
					memo[a*p]=max(memo[a*p],memo[a]);
				}
			}
		}
		cout<<num<<" "<<val<<endl;
		
	}
}

まとめ

シンプルな問題設定ながら、ぱっと解答が思いつかない。