yukicoder : No.990 N×Mマス計算（Kの倍数）

昔の★3の方が簡単？
https://yukicoder.me/problems/no/990

問題

２つの数列A,Bと正整数M、あと演算の種類opが与えられる。
opは加算または乗算である。

C[r][c] = A[r] op B[c]

として行列Cを作るとき、Mの倍数は何通りか。

解法

• 加算の場合
  • B[c]を総当たりし、A[r] % M = (M-B[c])%M であるものを数えればよい。これはあらかじめA[r]%Mの頻度を数えていれば容易。
• 乗算の場合
  • A[r] = GCD(A[r],M)、B[c] = GCD(A[c],M)で置き換え、それぞれ頻度を数えよう。
  • Mの約数の対(a,b)を列挙し、A[r]=aとなるrの数と、B[c]=bとなるcの数の積を数え上げればよい。

int H,W,K;
string S;
ll A[101000];
ll B[101000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K>>S;
	
	ll ret=0;
	if(S=="+") {
		map<int,int> M;
		FOR(x,W) {
			cin>>A[x];
			M[A[x]%K]++;
		}
		FOR(y,H) {
			cin>>B[y];
			ret+=M[(K-B[y]%K)%K];
		}
	}
	else {
		map<int,int> M,M2;
		FOR(x,W) {
			cin>>A[x];
			M[__gcd(A[x],(ll)K)]++;
		}
		FOR(y,H) {
			cin>>B[y];
			M2[__gcd(B[y],(ll)K)]++;
		}
		FORR(m,M) {
			FORR(m2,M2) {
				if(1LL*m.first*m2.first%K==0) ret+=1LL*m.second*m2.second;
			}
		}
	}
	
	cout<<ret<<endl;
	
}

まとめ

ここらへんは割とすんなり。