Hyperrectangle GCD
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MOD = (int)1e9 + 7;
int a[510];
int cnt[100100];
int inv[100100];
vector <int> ev[100100];
void add(int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}
int binpow(int a, int n) {
if (n == 0) return 1;
if (n % 2 == 1) return (long long)a * binpow(a, n - 1) % MOD;
int t = binpow(a, n / 2);
return (long long)t * t % MOD;
}
int clever(int* v, int n) {
int mx = *max_element(v, v + n);
memset(cnt, 0, 4 * (mx + 1));
for (int i = 1; i <= mx; i++) ev[i].clear();
for (int i = 0; i < n; i++) {
int bound = 1, cur = v[i];
while (cur > 0) {
int L = bound, R = v[i] + 1;
while (L + 1 < R) {
int M = (L + R) / 2;
if (v[i] / M < cur) {
R = M;
} else {
L = M;
}
}
ev[L].push_back(v[i]);
bound = L + 1;
cur = v[i] / (L + 1);
}
}
long long cur = 1;
for (int i = 0; i < n; i++) cur *= v[i], cur %= MOD;
for (int i = 1; i <= mx; i++) {
if (cur == 0) break;
cnt[i] = (int)cur;
if (i == mx) break;
for (int j = 0; j < ev[i].size(); j++) {
cur *= inv[ev[i][j] / i];
cur %= MOD;
cur *= (ev[i][j] / (i + 1));
cur %= MOD;
}
}
for (int i = mx; i >= 1; i--) {
for (int j = 2 * i; j <= mx; j += i) {
cnt[i] -= cnt[j];
if (cnt[i] < 0) {
cnt[i] += MOD;
}
}
}
int res = 0;
for (int i = 0; i <= mx; i++) add(res, (long long)cnt[i] * i % MOD);
return res;
}
int main() {
for (int i = 1; i < 100100; i++) {
inv[i] = binpow(i, MOD - 2);
}
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
printf("%d\n", clever(a, n));
}
return 0;
}
;;;;;;;
Lego Blocks
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define mo(m) if(m > 1000000007) m = m%1000000007
void solve(){
int t,hMax = 0,wMax = 0;
cin >> t;
vector <int> vH(t);
vector <int> vW(t);
for(int i = 0; i < t;i++){
cin >> vH[i] >> vW[i];
if(vH[i] > hMax)
hMax = vH[i];
if(vW[i] > wMax)
wMax = vW[i];
}
if(hMax < 4)
hMax = 4;
if(wMax < 4)
wMax = 4;
vector <int> rNumb(wMax + 1,0);
vector <vector <int> > rNumbPwh(hMax + 1,rNumb);
vector <vector <int> > rt(hMax + 1,rNumb);
vector <int> hNumb(hMax + 1,0);
for(int i = 0; i < t;i++){
if(vW[i] > hNumb[vH[i]])
hNumb[vH[i]] = vW[i];
}
rNumb[0] = 1;
rNumb[1] = 1;
rNumb[2] = 2;
rNumb[3] = 4;
rNumb[4] = 8;
for(int i = 5; i <= wMax; i++){
rNumb[i] += rNumb[i-4];
mo(rNumb[i]);
rNumb[i] += rNumb[i-3];
mo(rNumb[i]);
rNumb[i] += rNumb[i-2];
mo(rNumb[i]);
rNumb[i] += rNumb[i-1];
mo(rNumb[i]);
}
for(int i = 1; i <= wMax; i++){
long long rNumbTimes = rNumb[i];
for(int j = 1;j <= hMax ;j++){
rNumbPwh[j][i] = rNumbTimes;
rNumbTimes *= rNumb[i];
mo(rNumbTimes);
}
}
rt[1][1] = 1;
rt[1][2] = 1;
rt[1][3] = 1;
rt[1][4] = 1;
for(int i = 2 ; i <= hMax ; i++)
rt[i][1] = 1;
for(int j = 2;j <= hMax ;j++){
for(int i = 2; i <= hNumb[j]; i++){
long long rTemp = rNumbPwh[j][i];
for(int k = 1 ;k < i ; k++){
long long rTemp2 = ((long long) rt[j][k] )* ((long long) rNumbPwh[j][i-k]);
mo(rTemp2);
if(rTemp2 > rTemp){
rTemp = rTemp + 1000000007 - rTemp2;
}
else
rTemp -= rTemp2;
}
rt[j][i] = rTemp;
}
}
for(int i = 0; i < t;i++){
cout << rt[vH[i]][vW[i]]<<endl;
}
}
int main(){
solve();
return 0;
}
;;;;;;;;;
Largest Non-Coprime Submatrix
#include <bits/stdc++.h>using namespace std;int n, m;const int mx = 200;vector<int> h;int a[mx + 10][mx + 10];int b[mx + 10][mx + 10];vector<int> s;int Histogram(vector<int>& height){s.clear();height.push_back(0);int sum = 0;int i = 0;while (i < height.size()) {if (s.empty() || height[i] > height[s.back()]) {s.push_back(i);i++;}else {int t = s.back();s.pop_back();sum = max(sum, height[t] * (s.empty() ? i : i - s.back() - 1));}}return sum;}int isPrime(int x){int i;if (x < 2)return false;for (i = 2; i * i <= x; i++)if (x % i == 0)return false;return true;}int main(void){int i, j, k, kase = 0;cin >> n >> m;for (i = 0; i < n; i++)for (j = 0; j < m; j++)cin >> a[i][j];int prime;int ans = 0;h.resize(m, 0);for (prime = 0; prime < 10000; prime++) {if (!isPrime(prime))continue;for (i = 0; i < n; i++)for (j = 0; j < m; j++)b[i][j] = ((a[i][j] % prime) == 0);h.assign(m, 0);int base;for (base = 0; base < n; base++) {for (i = 0; i < m; i++) {if (b[base][i])h[i] += b[base][i];elseh[i] = 0;}ans = max(ans, Histogram(h));}}cout << ans << endl;return 0;};;;;;;;;;;;;;;;;;;;;;;
