yukicoder : No.991 N×Mマス計算（構築）

割と面倒な問題。
https://yukicoder.me/problems/no/991

問題

整数Nが与えられる。
100マス計算の要領で縦に設定した数列と横に設定した数列の積または和からなる２次元配列を構築したとき、

• 総和 mod X =N
• X以上の値がN個
• Xの倍数がN個

となるような数列とXと演算子を求めよ。

解法

Xの正の倍数を作ればX以上の値にもなる。
よって、X=N+1とし、基本的に縦横Xを敷き詰めて演算子を乗算としよう。
あとは総和のmod XをNにすればよいので、全体をNマスよりちょっと大きなマス数となるようにし、縦横一部要素をX未満として和がNとなるようにしよう。

以下では、1行目を1に固定し、いくつかの列をX未満にして、1行目と列の積の総和のmodがNとなるようにしている。

ll X;
ll N;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X;
	if(X==0) {
		cout<<"3 2 129"<<endl;
		cout<<"+ 12 34"<<endl;
		cout<<"10"<<endl;
		cout<<"20"<<endl;
		cout<<"30"<<endl;
		return;
	}
	
	ll K=X+1;
	x=1;
	for(x=1;x<=100000;x++) {
		for(y=max(1,x-2);y<=min(100000,x+2);y++) {
			if(1LL*x*y>X && 1LL*x*y-(x-1)<=X) {
				ll d=x*y-X;
				cout<<y<<" "<<x<<" "<<K<<endl;
				cout<<"*";
				FOR(i,d) {
					if(i==d-1) cout<<" "<<X;
					else cout<<" 1";
					X--;
				}
				FOR(i,x-d) cout<<" "<<K;
				cout<<endl;
				cout<<1<<endl;
				FOR(i,y-1) cout<<K<<endl;
				return;
			}
		}
	}
	
	
}

まとめ

これは992を先に解きたくなるよね。